Post-processing long pairwise alignments

Zheng Zhang, Piotr Berman, Thomas Wiehe, Webb Miller

    Research output: Contribution to journalArticlepeer-review

    31 Scopus citations


    Motivation: The local alignment problem for two sequences requires determining similar regions, one fr om 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. Availability: Software is available at

    Original languageEnglish (US)
    Pages (from-to)1012-1019
    Number of pages8
    Issue number12
    StatePublished - Dec 1999

    All Science Journal Classification (ASJC) codes

    • Statistics and Probability
    • Biochemistry
    • Molecular Biology
    • Computer Science Applications
    • Computational Theory and Mathematics
    • Computational Mathematics


    Dive into the research topics of 'Post-processing long pairwise alignments'. Together they form a unique fingerprint.

    Cite this