{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T19:10:16Z","timestamp":1734635416570,"version":"3.32.0"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 rely on a pre-computed library of pairwise alignments. This library will in general contain conflicting residue equivalences not all of which can be realized in the final MSTA. Hence to build a consistent MSTA, these methods have to select a conflict-free subset of equivalences.<\/jats:p><jats:p>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, Proc. 1st Ann. Int. Conf. Comput. Mol. Biol. (RECOMB-97), ACM Press, New York). This ILP formulation is a rigorous approach but its complexity is difficult to predict. The other method is T-Coffee (Notredame et al., 2000) 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.<\/jats:p><jats:p>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<\/jats:p><jats:p>Contact: \u00a0erik@sbc.su.se<\/jats:p>","DOI":"10.1093\/bioinformatics\/bti117","type":"journal-article","created":{"date-parts":[[2004,11,6]],"date-time":"2004-11-06T01:14:14Z","timestamp":1099703654000},"page":"1002-1009","source":"Crossref","is-referenced-by-count":5,"title":["Extracting multiple structural alignments from pairwise alignments: a comparison of a rigorous and a heuristic approach"],"prefix":"10.1093","volume":"21","author":[{"given":"Erik","family":"Sandelin","sequence":"first","affiliation":[{"name":"Stockholm Bioinformatics Center, AlbaNova, Stockholm University 106 91 Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2004,11,5]]},"reference":[{"key":"2023013107270673300_B1","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M. Complexity and Approximation1999, Berlin, Germany Springer-Verlag","DOI":"10.1007\/978-3-642-58412-1"},{"key":"2023013107270673300_B2","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L, Stein, C. Introduction to Algorithms2001 2nd edition , Cambridge, MA The MIT Press"},{"key":"2023013107270673300_B3","doi-asserted-by":"crossref","unstructured":"Dietmann, S., Park, J., Notredame, C., Heger, A., Lappe, M., Holm, L. 2001A fully automatic evolutionary classification of protein folds: Dali Domain Dictionary version 3. Nucleic Acids Res.29, pp. 55\u201357","DOI":"10.1093\/nar\/29.1.55"},{"key":"2023013107270673300_B4","unstructured":"Ding, D.F., Qian, J., Feng, Z.K. 1994A differential geometric treatment of protein structure comparison. Bull. Math. Biol.56923\u2013943"},{"key":"2023013107270673300_B5","doi-asserted-by":"crossref","unstructured":"Dror, O., Benyamini, H., Nussinov, R., Wolfson, H. 2003MASS: multiple structural alignment by secondary Structures. Bioinformatics19i95\u2013i104","DOI":"10.1093\/bioinformatics\/btg1012"},{"key":"2023013107270673300_B6","unstructured":"Eidhammer, I., Jonassen, I., Taylor, W.R. 2000Structure comparison and strcuture patterns. J. Comp. Bio.7685\u2013716"},{"key":"2023013107270673300_B7","doi-asserted-by":"crossref","unstructured":"Goldstein, H., Poole, C.P., Safko, J.L. Classical Mechanics2002 3rd edition , Boston, MA, USA Addison Wesley Publishing Company","DOI":"10.1119\/1.1484149"},{"key":"2023013107270673300_B8","doi-asserted-by":"crossref","unstructured":"Guda, C., Scheeff, E.D., Bourne, P.E., Shindyalov, P.E. 2001A new algorithm for the alignment of multiple protein structures using Monte Carlo optimization. Proc. Pacific Symp. Biocomput.6, pp. 275\u2013286","DOI":"10.1142\/9789814447362_0028"},{"key":"2023013107270673300_B9","unstructured":"Holm, L. and Sander, C. 1996Mapping the protein universe. Science273595\u2013602"},{"key":"2023013107270673300_B10","unstructured":"Kececioglu, J. 1993The maximum weight trace problem in multiple sequence alignment. Lecture Notes Comput. Sci.684106\u2013119"},{"key":"2023013107270673300_B11","unstructured":"Koehl, P. 2001Protein structure similarities. Curr. Opin. Struct. Biol.11348\u2013353"},{"key":"2023013107270673300_B12","doi-asserted-by":"crossref","unstructured":"Leibowitz, N., Nussinov, R., Wolfson, H.J. 2001MUSTA\u2014a general, efficient, automated method for multiple structure alignment and detection of common motifs: application to proteins. J. Comp. Bio.893\u2013121","DOI":"10.1089\/106652701300312896"},{"key":"2023013107270673300_B13","doi-asserted-by":"crossref","unstructured":"Levitt, M. and Gerstein, M. 1998A unified statistical framework for sequence comparison and structure comparison. Proc. Natl. Acad. Sci. USA955913\u20135920","DOI":"10.1073\/pnas.95.11.5913"},{"key":"2023013107270673300_B14","unstructured":"Murzin, A.G., Brenner, S.E., Hubbard, T., Chothia, C. 1995SCOP: a structural classification of proteins database for the investigation of sequences and structures. J. Mol. Biol.247536\u2013540"},{"key":"2023013107270673300_B15","unstructured":"Notredame, C., Higgins, D.G., Heringa, J. 2000T-Coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol.302205\u2013217"},{"key":"2023013107270673300_B16","doi-asserted-by":"crossref","unstructured":"Ochagav\u00eda, M.E. and Wodak, S. 2004Progressive combinatorial algorithm for multiple structural alignments: application to distantly related proteins. Proteins55436\u2013454","DOI":"10.1002\/prot.10587"},{"key":"2023013107270673300_B17","doi-asserted-by":"crossref","unstructured":"Orengo, C.A. and Taylor, W.R. 1996SSAP: sequential structure alignment program for protein structure comparison. Methods Enzymol.266617\u2013635","DOI":"10.1016\/S0076-6879(96)66038-8"},{"key":"2023013107270673300_B18","unstructured":"O'sullivan, O., Suhre, K., Abergel, C., Higgins, D.G., Notredame, C. 20043DCoffee: combining protein sequences and structures within multiple sequence alignments. J. Mol. Biol.340385\u2013395"},{"key":"2023013107270673300_B19","unstructured":"Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P. 1992Numerical Recipes in C. The Art of Scientific Computing , United Kingdom Cambridge University Press"},{"key":"2023013107270673300_B20","doi-asserted-by":"crossref","unstructured":"Reinert, K., Lenhof, H.-P., Mutzel, P., Mehlhorn, K., Kececioglu, J. 1997A branch-and-cut algorithm for multiple sequence alignment. Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB-97) , New York ACM Press, pp. , pp. 241\u2013249","DOI":"10.1145\/267521.267845"},{"key":"2023013107270673300_B21","doi-asserted-by":"crossref","unstructured":"Russell, R.B. and Barton, G.J. 1992Multiple protein sequence alignment from tertiary structure comparison: assignment of global and residue confidence levels. Proteins14309\u2013323","DOI":"10.1002\/prot.340140216"},{"key":"2023013107270673300_B22","unstructured":"\u0160ali, A. and Blundell, T.L. 1989Definition of general topological equivalence in protein structures. A procedure involving comparison of properties and relationships through simulated annealing and dynamic programming. J. Mol. Biol.212403\u2013428"},{"key":"2023013107270673300_B23","unstructured":"Shatsky, M., Nussinov, R., Wolfson, H.J. 2004A Method for simultaneous alignment of multiple protein structures. Proteins56143\u2013156"},{"key":"2023013107270673300_B24","unstructured":"Sillietoe, I. and Orengo, C. 2003Protein structure comparison. In Orengo, C.A., Jones, D.T., Thornton, J.M. (Eds.). Bioinformatics. Genes, Proteins & Computers , Oxford BIOS Scientific Publishers Ltd., pp. 81\u2013101"},{"key":"2023013107270673300_B25","doi-asserted-by":"crossref","unstructured":"Subbiah, S., Laurents, D.V., Levitt, M. 1993Structural similarity of DNA-binding domains of bacteriophage repressors and the globin core. Curr. Biol.3141\u2013148","DOI":"10.1016\/0960-9822(93)90255-M"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/1002\/48966521\/bioinformatics_21_7_1002.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/7\/1002\/48966521\/bioinformatics_21_7_1002.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T18:31:09Z","timestamp":1734633069000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/7\/1002\/268930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11,5]]},"references-count":25,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2005,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti117","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2005,4,1]]},"published":{"date-parts":[[2004,11,5]]}}}