Skip Navigation



Bioinformatics Advance Access published online on November 5, 2004
Bioinformatics, doi:10.1093/bioinformatics/bti117
Bioinformatics © Oxford University Press 2004; all rights reserved
This Article
Right arrow Advance Access manuscript (PDF) Freely available
Right arrow All Versions of this Article:
21/7/1002    most recent
bti117v1
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 Similar articles in PubMed
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 Sandelin, E.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Sandelin, E.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Received July 14, 2004
Revised October 20, 2004
Accepted October 20, 2004

Article

Extracting multiple structural alignments from pairwise alignments: a comparison of a rigorous and a heuristic approach

Erik Sandelin 1*

1 Stockholm Bioinformatics Center, AlbaNova, Stockholm University, 106 91 Stockholm, Sweden

* To whom correspondence should be addressed.
Erik Sandelin, E-mail: erik{at}sbc.su.se


  Abstract

Motivation: Multiple Structural Alignments (MSTAs) provide position-specific information on the sequence variability allowed by protein folds. This information can be exploited to better understand the evolution of proteins and the physical chemistry of polypeptide folding. Most MSTA methods relies on a pre-computed library of pairwise alignments. This library will in general contain conflicting residue equivalences which not all can be realized in the final MSTA. Hence to build a consistent MSTA these methods have to select a conflict-free subset of equivalences.

Results: Using a dataset with 327 families from SCOP 1.63 we compare the ability of two different methods to select an optimal conflict-free subset of equivalences. One is an implementation of Reinert et al.'s integer linear programming formulation (ILP) of the maximum weight trace problem (Reinert et al., 1997). This ILP formulation is a rigorous approach but its complexity is difficult to predict. The other method is T-Coffee which uses a heuristic enhancement of the equivalence weights which allow it to use the speed and simplicity of the progressive alignment approach while still incorporating information of all alignments in each step of building the MSTA. We find that although the ILP formulation consistently selects a more optimal set of conflict-free equivalences, the differences are small and the quality of the resulting MSTAs are essentially the same for both methods. Given its speed and predictable complexity, our results show that T-Coffee is an attractive alternative for producing high-quality MSTAs.

Availability: The software for Resolver, our implementation of Reinert et al.'s ILP formulation, and the dataset used in this study are available at http://www.sbc.su.se/~erik/resolver.


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
 BioinformaticsHome page
Y. Chen and G. M. Crippen
An iterative refinement algorithm for consistency based multiple structural alignment methods
Bioinformatics, September 1, 2006; 22(17): 2087 - 2093.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
J. Ebert and D. Brutlag
Development and validation of a consistency based multiple structure alignment algorithm
Bioinformatics, May 1, 2006; 22(9): 1080 - 1087.
[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.