Post-processing long pairwise alignments.
BACKGROUND
The local alignment problem for two sequences requires determining similar regions, one from each sequence, and aligning those regions. For alignments computed by dynamic programming, current approaches for selecting similar regions may have potential flaws. For instance, the criterion of Smith and Waterman can lead to inclusion of an arbitrarily poor internal segment. Other approaches can generate an alignment scoring less than some of its internal segments.


RESULTS
We develop an algorithm that decomposes a long alignment into sub-alignments that avoid these potential imperfections. Our algorithm runs in time proportional to the original alignment's length. Practical applications to alignments of genomic DNA sequences are described.
Zhang
Z
Z
Department of Computer Science and Engineering, Pennsylvania State University, University Park 16802, USA.
Berman
P
P
Wiehe
T
T
Miller
W
W
D000465:Algorithms; D000818:Animals; D006801:Humans; D051379:Mice; D009154:Mutation; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software