2024-07-19T20:43:06Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000336342024-03-29T05:26:34Z01164:02735:02796:02797
New Algorithms for Multiple Sequence AlignmentNew Algorithms for Multiple Sequence Alignmentjpnhttp://id.nii.ac.jp/1001/00033634/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=33634&item_no=1&attribute_id=1&file_no=1Copyright (c) 1998 by the Information Processing Society of JapanREAL WORLD COMPUTING PARTNERSHIP TSUKUBA MITSUI BLDG.PAUL, HORTONWe 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）1998105(1998-MPS-022)31361998-11-262009-06-30