Display Settings:

Format

Send to:

Choose Destination
See comment in PubMed Commons below
Proc Natl Acad Sci U S A. 2005 Jul 26;102(30):10557-62. Epub 2005 Jul 6.

An algorithm for progressive multiple alignment of sequences with insertions.

Author information

  • 1European Molecular Biology Laboratory-European Bioinformatics Institute, Hinxton CB10 1SD, United Kingdom. ari@ebi.ac.uk

Abstract

Dynamic programming algorithms guarantee to find the optimal alignment between two sequences. For more than a few sequences, exact algorithms become computationally impractical, and progressive algorithms iterating pairwise alignments are widely used. These heuristic methods have a serious drawback because pairwise algorithms do not differentiate insertions from deletions and end up penalizing single insertion events multiple times. Such an unrealistically high penalty for insertions typically results in overmatching of sequences and an underestimation of the number of insertion events. We describe a modification of the traditional alignment algorithm that can distinguish insertion from deletion and avoid repeated penalization of insertions and illustrate this method with a pair hidden Markov model that uses an evolutionary scoring function. In comparison with a traditional progressive alignment method, our algorithm infers a greater number of insertion events and creates gaps that are phylogenetically consistent but spatially less concentrated. Our results suggest that some insertion/deletion "hot spots" may actually be artifacts of traditional alignment algorithms.

Comment in

PMID:
16000407
[PubMed - indexed for MEDLINE]
PMCID:
PMC1180752
Free PMC Article

Images from this publication.See all images (4)Free text

Fig. 1.
Scheme 1.
Algorithm 1.
Fig. 2.
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

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