Near-Optimal Block Alignments

Kuo-Tsung TSENG  Chang-Biau YANG  Kuo-Si HUANG  Yung-Hsing PENG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.3   pp.789-795
Publication Date: 2008/03/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.3.789
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm Theory
Keyword: 
computational biology,  longest common subsequence,  biosequence alignment,  near-optimal alignments,  

Full Text: PDF(366.3KB)>>
Buy this Article




Summary: 
The optimal alignment of two given biosequences is mathematically optimal, but it may not be a biologically optimal one. To investigate more possible alignments with biological meaning, one can relax the scoring functions to get near-optimal alignments. Though the near optimal alignments increase the possibility of finding the correct alignment, they may confuse the biologists because the size of candidates is large. In this paper, we present the filter scheme for the near-optimal alignments. An easy method for tracing the near-optimal alignments and an algorithm for filtering those alignments are proposed. The time complexity of our algorithm is O(dmn) in the worst case, where d is the maximum distance between the near-optimal alignments and the optimal alignment, and m and n are the lengths of the input sequences, respectively.