Skip Navigation

This Article
Right arrow Full Text (Print PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Gotoh, O.
Right arrow Search for Related Content
PubMed
Right arrow Articles by Gotoh, O.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© Oxford University Press

Further improvement in methods of group-to-group sequence alignment with generalized profile operations

Osamu Gotoh

Department of Biochemistry, Saitama Cancer Center Research Institute 818 Komuro, Ina-machi, Saitama 362, Japan

It has previously been shown that rigorous optimization of alignment between two groups of sequences in the sense of minimal sum of pairs (SP) score with a linear gap-weighting function can be achieved by an extended version of the dynamic programming algorithm. The major drawback of this algorithm was that the computation time grows in proportion to the product of the numbers (M and N) of sequences comprising the two groups. A new algorithm presented in this paper achieves the same rigorous alignment in a time complexity much less dependent on the sizes of the groups. Examinations with many groups of sequences indicated that the new algorithm runs faster than the earlier one when MxN > 6–10, ~ 10 times faster when MxN 200, and > 100 times faster when MxN > 2500. This computational acceleration facilitates application of the algorithm to alignment of large groups, especially in the framework of iterative refinement strategies.

Received on July 27, 1993; accepted on February 23, 1994

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Protein Sci.Home page
R. I. Sadreyev, D. Baker, and N. V. Grishin
Profile-profile comparisons by COMPASS predict intricate homologies between protein families
Protein Sci., October 1, 2003; 12(10): 2262 - 2272.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.