{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T06:46:14Z","timestamp":1790491574000,"version":"4.1.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>While the pairwise alignments produced by sequence similarity searches are a powerful tool for identifying homologous proteins - proteins that share a common ancestor and a similar structure; pairwise sequence alignments often fail to represent accurately the structural alignments inferred from three-dimensional coordinates. Since sequence alignment algorithms produce optimal alignments, the best structural alignments must reflect suboptimal sequence alignment scores. Thus, we have examined a range of suboptimal sequence alignments and a range of scoring parameters to understand better which sequence alignments are likely to be more structurally accurate.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We compared near-optimal protein sequence alignments produced by the Zuker algorithm and a set of probabilistic alignments produced by the probA program with structural alignments produced by four different structure alignment algorithms. There is significant overlap between the solution spaces of structural alignments and both the near-optimal sequence alignments produced by commonly used scoring parameters for sequences that share significant sequence similarity (E-values &lt; 10<jats:sup>-5<\/jats:sup>) and the ensemble of probA alignments. We constructed a logistic regression model incorporating three input variables derived from sets of near-optimal alignments: robustness, edge frequency, and maximum bits-per-position. A ROC analysis shows that this model more accurately classifies amino acid pairs (edges in the alignment path graph) according to the likelihood of appearance in structural alignments than the robustness score alone. We investigated various trimming protocols for removing incorrect edges from the optimal sequence alignment; the most effective protocol is to remove matches from the semi-global optimal alignment that are outside the boundaries of the local alignment, although trimming according to the model-generated probabilities achieves a similar level of improvement. The model can also be used to generate novel alignments by using the probabilities in lieu of a scoring matrix. These alignments are typically better than the optimal sequence alignment, and include novel correct structural edges. We find that the probA alignments sample a larger variety of alignments than the Zuker set, which more frequently results in alignments that are closer to the structural alignments, but that using the probA alignments as input to the regression model does not increase performance.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>The pool of suboptimal pairwise protein sequence alignments substantially overlaps structure-based alignments for pairs with statistically significant similarity, and a regression model based on information contained in this alignment pool improves the accuracy of pairwise alignments with respect to structure-based alignments.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-11-146","type":"journal-article","created":{"date-parts":[[2010,3,23]],"date-time":"2010-03-23T07:15:01Z","timestamp":1269328501000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Improving pairwise sequence alignment accuracy using near-optimal protein sequence alignments"],"prefix":"10.1186","volume":"11","author":[{"given":"Michael L","family":"Sierk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael E","family":"Smoot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ellen J","family":"Bass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William R","family":"Pearson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,3,22]]},"reference":[{"key":"3603_CR1","doi-asserted-by":"publisher","first-page":"6073","DOI":"10.1073\/pnas.95.11.6073","volume":"95","author":"SE Brenner","year":"1998","unstructured":"Brenner SE, Chothia C, Hubbard TJ: Assessing sequence comparison methods with reliable structurally identified distant evolutionary relationships. Proceedings of the National Academy of Sciences USA 1998, 95: 6073\u20136078. 10.1073\/pnas.95.11.6073","journal-title":"Proceedings of the National Academy of Sciences USA"},{"issue":"Suppl 6","key":"3603_CR2","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1002\/prot.10591","volume":"53","author":"C Venclovas","year":"2003","unstructured":"Venclovas C: Comparative modeling in CASP5: progress is evident, but alignment errors remain a significant hindrance. Proteins 2003, 53(Suppl 6):380\u2013388. 10.1002\/prot.10591","journal-title":"Proteins"},{"key":"3603_CR3","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1038\/88640","volume":"8","author":"D Vitkup","year":"2001","unstructured":"Vitkup D, Melamud E, Moult J, Sander C: Completeness in structural genomics. Nat Struct Biol 2001, 8: 559\u2013566. 10.1038\/88640","journal-title":"Nat Struct Biol"},{"key":"3603_CR4","doi-asserted-by":"publisher","first-page":"1702","DOI":"10.1110\/ps.4820102","volume":"11","author":"L Jaroszewski","year":"2002","unstructured":"Jaroszewski L, Li W, Godzik A: In search for more accurate alignments in the twilight zone. Protein Sci 2002, 11: 1702\u20131713. 10.1110\/ps.4820102","journal-title":"Protein Sci"},{"key":"3603_CR5","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 1970, 48: 443\u2013453. 10.1016\/0022-2836(70)90057-4","journal-title":"Journal of Molecular Biology"},{"key":"3603_CR6","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0025-5564(85)90096-3","volume":"77","author":"MS Waterman","year":"1985","unstructured":"Waterman MS, Byers TH: A dynamic programming algorithm to find all solutions in a neighborhood of the optimum. Mathematical Biosciences 1985, 77: 179\u2013188. 10.1016\/0025-5564(85)90096-3","journal-title":"Mathematical Biosciences"},{"key":"3603_CR7","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/0022-2836(91)90667-U","volume":"219","author":"MA Saqi","year":"1991","unstructured":"Saqi MA, Sternberg MJ: A simple method to generate non-trivial alternate alignments of protein sequences. J Mol Biol 1991, 219: 727\u2013732. 10.1016\/0022-2836(91)90667-U","journal-title":"J Mol Biol"},{"key":"3603_CR8","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/0022-2836(91)80062-Y","volume":"221","author":"M Zuker","year":"1991","unstructured":"Zuker M: Suboptimal sequence alignment in molecular biology. Alignment with error analysis. J Mol Biol 1991, 221: 403\u2013420. 10.1016\/0022-2836(91)80062-Y","journal-title":"J Mol Biol"},{"key":"3603_CR9","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1093\/protein\/7.9.1059","volume":"7","author":"RH Lathrop","year":"1994","unstructured":"Lathrop RH: The protein threading problem with sequence amino acid interaction preferences is NP-complete. Protein Eng 1994, 7: 1059\u20131068. 10.1093\/protein\/7.9.1059","journal-title":"Protein Eng"},{"key":"3603_CR10","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1089\/cmb.1998.5.493","volume":"5","author":"I Holmes","year":"1998","unstructured":"Holmes I, Durbin R: Dynamic programming alignment accuracy. J Comput Biol 1998, 5: 493\u2013504. 10.1089\/cmb.1998.5.493","journal-title":"J Comput Biol"},{"key":"3603_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/jtbi.1995.0085","volume":"174","author":"MQ Zhang","year":"1995","unstructured":"Zhang MQ, Marr TG: Alignment of molecular sequences seen as random path analysis. J Theor Biol 1995, 174: 119\u2013129. 10.1006\/jtbi.1995.0085","journal-title":"J Theor Biol"},{"key":"3603_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1089\/10665270152530845","volume":"8","author":"YK Yu","year":"2001","unstructured":"Yu YK, Hwa T: Statistical significance of probabilistic sequence alignment and related local hidden Markov models. J Comput Biol 2001, 8: 249\u2013282. 10.1089\/10665270152530845","journal-title":"J Comput Biol"},{"key":"3603_CR13","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1016\/j.jmb.2003.08.015","volume":"333","author":"B Knudsen","year":"2003","unstructured":"Knudsen B, Miyamoto MM: Sequence alignments and pair hidden Markov models using evolutionary history. J Mol Biol 2003, 333: 453\u2013460. 10.1016\/j.jmb.2003.08.015","journal-title":"J Mol Biol"},{"key":"3603_CR14","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1093\/bioinformatics\/18.suppl_2.S153","volume":"18","author":"U Muckstein","year":"2002","unstructured":"Muckstein U, Hofacker I, Stadler P: Stochastic pairwise alignments. Binformatics 2002, 18: 153\u2013160.","journal-title":"Binformatics"},{"key":"3603_CR15","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1093\/bioinformatics\/18.2.306","volume":"18","author":"M Cline","year":"2002","unstructured":"Cline M, Hughey R, Karplus K: Predicting reliable regions in protein sequence alignments. Bioinformatics 2002, 18: 306\u2013314. 10.1093\/bioinformatics\/18.2.306","journal-title":"Bioinformatics"},{"key":"3603_CR16","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1089\/cmb.1999.6.253","volume":"6","author":"L Yu","year":"1999","unstructured":"Yu L, Smith TF: Positional statistical significance in sequence alignment. J Comput Biol 1999, 6: 253\u2013259. 10.1089\/cmb.1999.6.253","journal-title":"J Comput Biol"},{"key":"3603_CR17","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1093\/protein\/8.10.999","volume":"8","author":"S Miyazawa","year":"1995","unstructured":"Miyazawa S: A reliable sequence alignment method based on probabilities of residue correspondences. Protein Eng 1995, 8: 999\u20131009. 10.1093\/protein\/8.10.999","journal-title":"Protein Eng"},{"key":"3603_CR18","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1093\/protein\/9.2.127","volume":"9","author":"HT Mevissen","year":"1996","unstructured":"Mevissen HT, Vingron M: Quantifying the local reliability of a sequence alignment. Protein Engineering 1996, 9: 127\u2013132. 10.1093\/protein\/9.2.127","journal-title":"Protein Engineering"},{"key":"3603_CR19","first-page":"387","volume":"9","author":"KM Chao","year":"1993","unstructured":"Chao KM, Hardison RC, Miller W: Locating well-conserved regions within a pairwise alignment. Comput Appl Biosci 1993, 9: 387\u2013396.","journal-title":"Comput Appl Biosci"},{"key":"3603_CR20","doi-asserted-by":"publisher","DOI":"10.1002\/0471722146","volume-title":"Applied Logistic Regression","author":"DW Hosmer","year":"2000","unstructured":"Hosmer DW, Lemeshow S: Applied Logistic Regression. New York: John Wiley & Sons, Inc; 2000. full_text"},{"key":"3603_CR21","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1093\/bioinformatics\/bth013","volume":"20","author":"ME Smoot","year":"2004","unstructured":"Smoot ME, Guerlain SA, Pearson WR: Visualization of near-optimal sequence alignments. Bioinformatics 2004, 20: 953\u2013958. 10.1093\/bioinformatics\/bth013","journal-title":"Bioinformatics"},{"key":"3603_CR22","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1057\/palgrave.ivs.9500100","volume":"4","author":"ME Smoot","year":"2005","unstructured":"Smoot ME, Bass EJ, Guerlain SA, Pearson WR: A system for visualizing and analyzing near-optimal protein sequence alignments. Information Visualization 2005, 4: 224\u2013237. 10.1057\/palgrave.ivs.9500100","journal-title":"Information Visualization"},{"key":"3603_CR23","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1126\/science.273.5275.595","volume":"273","author":"L Holm","year":"1996","unstructured":"Holm L, Sander C: Mapping the protein universe. Science 1996, 273: 595\u2013603. 10.1126\/science.273.5275.595","journal-title":"Science"},{"key":"3603_CR24","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1093\/bioinformatics\/16.6.566","volume":"16","author":"L Holm","year":"2000","unstructured":"Holm L, Park J: DaliLite workbench for protein structure comparison. Bioinformatics 2000, 16: 566\u2013567. 10.1093\/bioinformatics\/16.6.566","journal-title":"Bioinformatics"},{"key":"3603_CR25","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1093\/protein\/11.9.739","volume":"11","author":"IN Shindyalov","year":"1998","unstructured":"Shindyalov IN, Bourne PE: Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Eng 1998, 11: 739\u2013747. 10.1093\/protein\/11.9.739","journal-title":"Protein Eng"},{"key":"3603_CR26","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1107\/S0907444995016477","volume":"52","author":"GJ Kleywegt","year":"1996","unstructured":"Kleywegt GJ: Use of non-crystallographic symmetry in protein structure refinement. Acta Crystallogr D Biol Crystallogr 1996, 52: 842\u2013857. 10.1107\/S0907444995016477","journal-title":"Acta Crystallogr D Biol Crystallogr"},{"key":"3603_CR27","doi-asserted-by":"publisher","first-page":"5913","DOI":"10.1073\/pnas.95.11.5913","volume":"95","author":"M Levitt","year":"1998","unstructured":"Levitt M, Gerstein M: A unified statistical framework for sequence cdent, but alignment errors remain a. Proc Natl Acad Sci USA 1998, 95: 5913\u20135920. 10.1073\/pnas.95.11.5913","journal-title":"Proc Natl Acad Sci USA"},{"key":"3603_CR28","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1002\/1097-0134(20001001)41:1<108::AID-PROT130>3.0.CO;2-S","volume":"41","author":"T Kawabata","year":"2000","unstructured":"Kawabata T, Nishikawa K: Protein structure comparison using the markov transition model of evolution. Proteins 2000, 41: 108\u2013122. 10.1002\/1097-0134(20001001)41:1<108::AID-PROT130>3.0.CO;2-S","journal-title":"Proteins"},{"key":"3603_CR29","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1016\/S0969-2126(97)00260-8","volume":"5","author":"CA Orengo","year":"2003","unstructured":"Orengo CA, Michie AD, Jones S, Jones DT, Swindells MB, Thornton JM: CATH--a hierarchic classification of protein domain structures. Structure 2003, 5: 1093\u20131108. 10.1016\/S0969-2126(97)00260-8","journal-title":"Structure"},{"key":"3603_CR30","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1016\/0888-7543(91)90071-L","volume":"11","author":"WR Pearson","year":"1991","unstructured":"Pearson WR: Searching protein sequence libraries: comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithms. Genomics 1991, 11: 635\u2013650. 10.1016\/0888-7543(91)90071-L","journal-title":"Genomics"},{"key":"3603_CR31","unstructured":"R: A language and environment for statistical computing[http:\/\/www.R-project.org]"},{"key":"3603_CR32","unstructured":"Design: R Package version 2.0\u20139[http:\/\/biostat.mc.vanderbilt.edu\/s\/Design]"},{"key":"3603_CR33","first-page":"5","volume":"14","author":"H Aikake","year":"1976","unstructured":"Aikake H: An Information Criterion. Mathematical Sciences 1976, 14: 5\u20139.","journal-title":"Mathematical Sciences"},{"key":"3603_CR34","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1080\/01621459.1952.10483441","volume":"47","author":"W Kruskal","year":"1952","unstructured":"Kruskal W, Wallis W: Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association 1952, 47: 583\u2013621. 10.2307\/2280779","journal-title":"Journal of the American Statistical Association"},{"key":"3603_CR35","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1002\/(SICI)1097-0258(19970515)16:9<965::AID-SIM509>3.0.CO;2-O","volume":"16","author":"DW Hosmer","year":"1997","unstructured":"Hosmer DW, Hosmer T, Le Cessie S, Lemeshow S: A comparison of goodness-of-fit tests for the logistic regression model. Stat Med 1997, 16: 965\u2013980. 10.1002\/(SICI)1097-0258(19970515)16:9<965::AID-SIM509>3.0.CO;2-O","journal-title":"Stat Med"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-11-146.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T05:19:32Z","timestamp":1630473572000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-11-146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,22]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["3603"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-11-146","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,22]]},"assertion":[{"value":"27 July 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"146"}}