A general method for fast multiple sequence alignment

Tönges U, Perrey SW, Stoye J, Dress A (1996)
Gene 172(1): GC33-GC41.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Tönges, Udo; Perrey, Sören W.; Stoye, JensUniBi ; Dress, AndreasUniBi
Abstract / Bemerkung
We have developed a fast heuristic algorithm for multiple sequence alignment which provides near-to-optimal results for sufficiently homologous sequences. The algorithm makes use of the standard dynamic programming procedure by applying it to all pairs of sequences. The resulting score matrices for pair-wise alignment give rise to secondary matrices containing the additional charges imposed by forcing the alignment path to run through a particular vertex. Such a constraint corresponds to slicing the sequences at the positions defining that vertex, and aligning the remaining pairs of prefix and suffix sequences separately. From these secondary matrices, one can compute - for any given family of sequences - suitable positions for cutting all of these sequences simultaneously, thus reducing the problem of aligning a family of n sequences of average length l in a Divide and Conquer fashion to aligning two families of n sequences of approximately half that length. In this paper, we explain the method for the case of 3 sequences in detail, and we demonstrate its potential and its limits by discussing its behaviour for several test families. A generalization for aligning more than 3 sequences is lined out, and some actual alignments constructed by our algorithm for various user-defined parameters are presented.
Secondary matrix; Pair-wise sequence alignment; Divide and conquer; Multiple sequence alignment; Dynamic programming
Page URI


Tönges U, Perrey SW, Stoye J, Dress A. A general method for fast multiple sequence alignment. Gene. 1996;172(1):GC33-GC41.
Tönges, U., Perrey, S. W., Stoye, J., & Dress, A. (1996). A general method for fast multiple sequence alignment. Gene, 172(1), GC33-GC41. doi:10.1016/0378-1119(96)00123-0
Tönges, U., Perrey, S. W., Stoye, J., and Dress, A. (1996). A general method for fast multiple sequence alignment. Gene 172, GC33-GC41.
Tönges, U., et al., 1996. A general method for fast multiple sequence alignment. Gene, 172(1), p GC33-GC41.
U. Tönges, et al., “A general method for fast multiple sequence alignment”, Gene, vol. 172, 1996, pp. GC33-GC41.
Tönges, U., Perrey, S.W., Stoye, J., Dress, A.: A general method for fast multiple sequence alignment. Gene. 172, GC33-GC41 (1996).
Tönges, Udo, Perrey, Sören W., Stoye, Jens, and Dress, Andreas. “A general method for fast multiple sequence alignment”. Gene 172.1 (1996): GC33-GC41.

11 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

The relative sensitivity of different alignment methods and character codings in sensitivity analysis
Simmons MarkP, Müller KaiF, Webb ColleenT., Cladistics 24(6), 2008
PMID: IND44127586
Global multiple-sequence alignment with repeats.
Sammeth M, Heringa J., Proteins 64(1), 2006
PMID: 16609972
Detailed protein sequence alignment based on Spectral Similarity Score (SSS).
Gupta K, Thomas D, Vidya SV, Venkatesh KV, Ramakumar S., BMC Bioinformatics 6(), 2005
PMID: 15850477

38 References

Daten bereitgestellt von Europe PubMed Central.

Introduction to Computational Biology
Waterman, 1995

A survey of multiple sequence comparison methods.
Chan SC, Wong AK, Chiu DK., Bull. Math. Biol. 54(4), 1992
PMID: 1591533
An overview of sequence comparison algorithms in molecular biology
Myers, 1991
Simultaneous comparison of three protein sequences
Murata, 1985
Three-way Needleman-Wunsch algorithm
Murata, 1990
The Multiple Sequence Alignment Problem in Biology.
Carrillo H, Lipman D., SIAM J Appl Math 48(5), 1988
PMID: c6805
Alignment of three sequences in quadratic space
Huang, Appl. Comput. Rev. 1(2), 1993
A fast algorithm for the optimal alignment of three strings.
Allison L., J. Theor. Biol. 164(2), 1993
PMID: 8246519
A flexible method to align large numbers of biological sequences.
Taylor WR., J. Mol. Evol. 28(1-2), 1988
PMID: 3148736
The maximum weight trace problem in multiple sequence alignment
Kececioglu, 1993
Approximation algorithms for multiple sequence alignment
Bafna, 1994
Progressive sequence alignment as a prerequisite to correct phylogenetic trees.
Feng DF, Doolittle RF., J. Mol. Evol. 25(4), 1987
PMID: 3118049
MASCOT: multiple alignment system for protein sequences based on three-way dynamic programming.
Hirosawa M, Hoshida M, Ishikawa M, Toya T., Comput. Appl. Biosci. 9(2), 1993
PMID: 8481818
A method for the simultaneous alignment of three or more amino acid sequences.
Johnson MS, Doolittle RF., J. Mol. Evol. 23(3), 1986
PMID: 3100815
Multiple sequence alignment by a pairwise algorithm.
Taylor WR., Comput. Appl. Biosci. 3(2), 1987
PMID: 3453222
Line geometries for sequence comparisons
Waterman, Bull. Math. Biol. 48(), 1984
Gap costs for multiple sequence alignment.
Altschul SF., J. Theor. Biol. 138(3), 1989
PMID: 2593679
A divide and conquer approach to multiple alignment
Dress, 1995
A linear space algorithm for computing maximal common subsequences
Hirschberg, Commun. ACM 18(6), 1975
Determination of reliable regions in protein sequence alignments.
Vingron M, Argos P., Protein Eng. 3(7), 1990
PMID: 2217130
On near-optimal alignments of biological sequences
Naor, J. Comp. Biol. 1(4), 1994
Weights for data related by a tree.
Altschul SF, Carroll RJ, Lipman DJ., J. Mol. Biol. 207(4), 1989
PMID: 2760928
Weighting in sequence space: a comparison of methods in terms of generalized sequences
Vingron, 1993
A tool for multiple sequence alignment
Lipman, 1989
Improving the practical space and time efficiency of the shortest-Paths approach to sum-of-pairs multiple sequence alignment
Gupta, J. Comp. Biol. 2(3), 1995
Optimal alignments in linear space.
Myers EW, Miller W., Comput. Appl. Biosci. 4(1), 1988
PMID: 3382986
On the complexity of multiple sequence alignment
Wang, J. Comp. Biol. 1(4), 1994
Unified approach to alignment and phylogenies
Hein, 1990
Medians in median graphs
Bandelt, Discr. Appl. Math. 8(), 1984
Frequency of insertion-deletion, transversion and transition in the evolution of 5S ribosomal RNA
Sankoff, J. Mol. Biol. 7(), 1976
Towards integration of multiple alignment and phylogenetic tree reconstruction
Vingron, Arbeitspapiere 852(), 1994


Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®


PMID: 8654965
PubMed | Europe PMC

Suchen in

Google Scholar