頁籤選單縮合
題 名 | The Better Alignment among Output Alignments |
---|---|
作 者 | Tseng, Kuo-tsung; Yang, Chang-biau; Huang, Kuo-si; | 書刊名 | Journal of Computers |
卷 期 | 18:3 2007.10[民96.10] |
頁 次 | 頁51-61 |
分類號 | 368 |
關鍵詞 | Bioinformatics; Computational biology; Longest common subsequence; Biosequence alignment; |
語 文 | 英文(English) |
英文摘要 | In nowadays molecular biology, the biosequence alignment is one of the most fundamental techniques. It can be mapped into the longest common subsequence problem, which can be solved in O(□□) time with the dynamic programming technique, where □ and □ are the lengths of the two biosequences. In fact, the reasonability of an alignment of two biosequences depends on the scoring function used by the algorithm. Scientists have presented many scoring functions to measure the goodness of the alignments in different criteria, such as the affine gap penalty, and score matrices like PAMs, Blosums, Gonnets. All of these scoring functions are based on the same core, the dynamic programming. Once the optimal alignment score is found, tracing back the alignment lattice, which is produced during the dynamic programming, will obtain the alignment of the optimal score. Unfortunately, the optimal alignment may not be unique in most cases and the most biologically meaningful alignment may not be an optimal alignment. In this paper, we present some mathematical scoring criteria that should help in finding the better, according to biological considerations, alignment among output (optimal) alignments of the original LCS algorithm and illustrate our algorithms to solve them. Our algorithms give not only the alignment of the optimal score but also more biologically meaningful without increasing the computing complexity of the original algorithm. |
本系統中英文摘要資訊取自各篇刊載內容。