A novel randomized iterative strategy for aligning multiple protein sequences
Analytical Biostatistics Section, Division of Computer Research and Technology, (formerly, Laboratory of Theoretical and Physical Biology, National Institute of Child Health) National Institutes of Health Building 12A, Room 2009, Bethesda, MD 20892, USA
1To whom reprint requests should be sent
The rigorous alignment of multiple protein sequences becomes impractical even with a modest number of sequences, since computer memory and time requirements increase as the product of the lengths of the sequences. We have devised a strategy to approach such an optimal alignment, which modifies the intensive computer storage and time requirements of dynamic programming. Our algorithm randomly divides a group of unaligned sequences into two subgroups, between which an optimal alignment is then obtained by a Needleman — Wunsch style of algorithm. Our algorithm uses a matrix with dimensions corresponding to the lengths of the two aligned sequence subgroups. The pairwise alignment process is repeated using different random divisions of the whole group into two subgroups. Compared with the rigorous approach of solving the n-dimensional lattice by dynamic programming, our iterative algorithm results in alignments that match or are close to the optimal solution, on a limited set of test problems. We have implemented this algorithm in a computer program that runs on the IBM PC class of machines, together with a user-friendly environment for interactively selecting sequences or groups of sequences to be aligned either simultaneously or progressively.
Received on December 1, 1990; accepted on April 20, 1991
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  K. Katoh and H. Toh Recent developments in the MAFFT multiple sequence alignment program Brief Bioinform, July 1, 2008; 9(4): 286 - 298. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Chakrabarti, C. J. Lanczycki, A. R. Panchenko, T. M. Przytycka, P. A. Thiessen, and S. H. Bryant Refining multiple sequence alignments with conserved core regions. Nucleic Acids Res., January 1, 2006; 34(9): 2598 - 2606. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. D. Costache, P. K. Pullela, P. Kasha, H. Tomasiewicz, and D. S. Sem Homology-Modeled Ligand-Binding Domains of Zebrafish Estrogen Receptors {alpha}, {beta}1, and {beta}2: From in Silico to in Vivo Studies of Estrogen Interactions in Danio rerio as a Model System Mol. Endocrinol., December 1, 2005; 19(12): 2979 - 2990. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. B. Do, M. S.P. Mahabhashyam, M. Brudno, and S. Batzoglou ProbCons: Probabilistic consistency-based multiple sequence alignment Genome Res., February 1, 2005; 15(2): 330 - 340. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Katoh, K.-i. Kuma, H. Toh, and T. Miyata MAFFT version 5: improvement in accuracy of multiple sequence alignment Nucleic Acids Res., January 20, 2005; 33(2): 511 - 518. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Katoh, K. Misawa, K.-i. Kuma, and T. Miyata MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform Nucleic Acids Res., July 15, 2002; 30(14): 3059 - 3066. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. Matsuda, K. Ishii, P. Bourvagnet, K.-i. Kuma, H. Hayashida, T. Miyata, and T. Honjo The Complete Nucleotide Sequence of the Human Immunoglobulin Heavy Chain Variable Region Locus J. Exp. Med., December 7, 1998; 188(11): 2151 - 2162. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Arakawa, K.-i. Kuma, M. Yasuda, S. Furusawa, S. Ekino, and H. Yamagishi Oligoclonal Development of B Cells Bearing Discrete Ig Chains in Chicken Single Germinal Centers J. Immunol., May 1, 1998; 160(9): 4232 - 4241. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Urade, T. Tanaka, N. Eguchi, M. Kikuchi, H. Kimura, H. Toh, and O. Hayaishi Structural and Functional Significance of Cysteine Residues of Glutathione-independent Prostaglandin D Synthase J. Biol. Chem., January 20, 1995; 270(3): 1422 - 1428. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Lawrence, S. Altschul, M. Boguski, J. Liu, A. Neuwald, and J. Wootton Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment Science, October 8, 1993; 262(5131): 208 - 214. [Abstract] [PDF]
|
|