Send to:

Choose Destination
See comment in PubMed Commons below
Bioinformatics. 1999 Dec;15(12):1012-9.

Post-processing long pairwise alignments.

Author information

  • 1Department of Computer Science and Engineering, Pennsylvania State University, University Park 16802, USA.



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.


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.

[PubMed - indexed for MEDLINE]
Free full text

LinkOut - more resources

Full Text Sources

Other Literature Sources

PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for HighWire
    Loading ...
    Write to the Help Desk