http://swrc.ontoware.org/ontology#TechnicalReport
New Algorithms for Multiple Sequence Alignment
ja
REAL WORLD COMPUTING PARTNERSHIP TSUKUBA MITSUI BLDG.
PAUL HORTON
We have developed two new exact algorithms for gapless multiple alignment of DNA sequences. Unlike previous exact algorithms for sufficiently short motifs the complexity of our algorithms do not grow exponentially in the number of sequences. One algorithm which assumes a class of scoring functions which includes the information theoretic entry scoring function is polynomial in the number of sequences although it is exponential in the width of the motifs to be aligned. The other algorithm is super exponential in the width of the motif but linear in the number of sequences for a very general class of scoring functions.
We have developed two new exact algorithms for gapless multiple alignment of DNA sequences. Unlike previous exact algorithms, for sufficiently short motifs, the complexity of our algorithms do not grow exponentially in the number of sequences. One algorithm, which assumes a class of scoring functions which includes the information theoretic entry scoring function, is polynomial in the number of sequences although it is exponential in the width of the motifs to be aligned. The other algorithm is super exponential in the width of the motif but linear in the number of sequences for a very general class of scoring functions.
AN10505667
情報処理学会研究報告数理モデル化と問題解決（MPS）
1998
105(1998-MPS-022)
31-36
1998-11-26