Alignments without low-scoring regions

Zheng Zhang, Piotr Berman, Webb Miller

    Research output: Contribution to conferencePaperpeer-review

    3 Scopus citations

    Abstract

    Given a strong match between regions of two sequences, how far can the match be meaningfully extended if gaps are allowed in the resulting alignment? The aim is to avoid searching beyond the point that a useful extension of the alignment is likely to be found. Without loss of generality, we can restrict attention to the suffixes of the sequences that follow the strong match, which leads to the following formal problem. Given two sequences and a fixed X>0, align initial portions of the sequences subject to the constraint that no section of the alignment scores below -X. Our results indicate that computing an optimal alignment under this constraint is very expensive. However, less rigorous conditions on the alignment can be guaranteed by quite efficient algorithms. One of these variants has been implemented in a new release of the Blast suite of database search programs.

    Original languageEnglish (US)
    Pages294-301
    Number of pages8
    DOIs
    StatePublished - 1998
    EventProceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology - New York, NY, USA
    Duration: Mar 22 1998Mar 25 1998

    Other

    OtherProceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology
    CityNew York, NY, USA
    Period3/22/983/25/98

    All Science Journal Classification (ASJC) codes

    • General Computer Science
    • General Biochemistry, Genetics and Molecular Biology

    Fingerprint

    Dive into the research topics of 'Alignments without low-scoring regions'. Together they form a unique fingerprint.

    Cite this