A general method for fast multiple sequence alignment

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

Journal Article | Published | English

No fulltext has been uploaded

Author
; ; ;
Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

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.
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.
This data publication is cited in the following publications:
This publication cites the following data publications:

10 Citations in Europe PMC

Data provided by Europe PubMed Central.

The relative sensitivity of different alignment methods and character codings in sensitivity analysis
Simmons MarkP, Muller KaiF, Webb ColleenT., Cladistics 24(6), 2008
PMID: IND44127586
Dynamic programming algorithms for comparing multineuronal spike trains via cost-based metrics and alignments.
Victor JD, Goldberg DH, Gardner D., J. Neurosci. Methods 161(2), 2007
PMID: 17174403
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
Multiple sequence alignment: algorithms and applications.
Gotoh O., Adv. Biophys. 36(), 1999
PMID: 10463075

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 8654965
PubMed | Europe PMC

Search this title in

Google Scholar