{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:07:10Z","timestamp":1782968830861,"version":"3.54.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,4,30]],"date-time":"2007-04-30T00:00:00Z","timestamp":1177891200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2007,12]]},"DOI":"10.1186\/1471-2105-8-140","type":"journal-article","created":{"date-parts":[[2007,4,30]],"date-time":"2007-04-30T15:57:55Z","timestamp":1177948675000},"source":"Crossref","is-referenced-by-count":2,"title":["Lower bounds on multiple sequence alignment using exact 3-way alignment"],"prefix":"10.1186","volume":"8","author":[{"given":"Charles J","family":"Colbourn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudhir","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,4,30]]},"reference":[{"key":"1512_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1109\/BIBE.2001.974411","volume-title":"Proceedings of The 2nd IEEE International Symposium on Bioinformatics and Bioengineering (BIBE'2001)","author":"A Davidson","year":"2001","unstructured":"Davidson A: A Fast Pruning Algorithm for Optimal Sequence Alignment. Proceedings of The 2nd IEEE International Symposium on Bioinformatics and Bioengineering (BIBE'2001). 2001, 49-56."},{"key":"1512_CR2","first-page":"823","volume":"264","author":"O Gotoh","year":"1996","unstructured":"Gotoh O: Significant Improvement in Accuracy of Multiple Protein Sequence Alignments by Iterative Refinement as Assessed by Reference to Structural Alignments. J Mol Evol. 1996, 264: 823-838.","journal-title":"J Mol Evol"},{"key":"1512_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02460299","volume":"55","author":"D Gusfield","year":"1993","unstructured":"Gusfield D: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin Mathematical Biology. 1993, 55: 141-154.","journal-title":"Bulletin Mathematical Biology"},{"key":"1512_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. 1997, Cambridge University Press"},{"key":"1512_CR5","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/381771.381773","volume":"1","author":"X Huang","year":"1993","unstructured":"Huang X: Alignment of Three Sequences in Quadratic Space. ACM SIGAPP Applied Computing Review. 1993, 1: 7-11.","journal-title":"ACM SIGAPP Applied Computing Review"},{"key":"1512_CR6","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1093\/bioinformatics\/9.2.169","volume":"9","author":"W Miller","year":"1993","unstructured":"Miller W: Building multiple alignments from pairwise alignments. Bioinformatics. 1993, 9: 169-176.","journal-title":"Bioinformatics"},{"key":"1512_CR7","first-page":"11","volume":"4","author":"EW Myers","year":"1988","unstructured":"Myers EW, Miller W: Optimal alignments in linear space. Comput Appl Biosci. 1988, 4: 11-17.","journal-title":"Comput Appl Biosci"},{"key":"1512_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(99)00324-2","volume":"259","author":"P Bonizzoni","year":"2001","unstructured":"Bonizzoni P, Vedova GD: The complexity of multiple sequence alignment with SP-score that is a metric. Theoretical Computer Science. 2001, 259: 63-79.","journal-title":"Theoretical Computer Science"},{"key":"1512_CR9","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1089\/106652701753307511","volume":"8","author":"W Just","year":"2001","unstructured":"Just W: Computational complexity of multiple sequence alignment using SP score. J Comput Biol. 2001, 8: 615-623.","journal-title":"J Comput Biol"},{"key":"1512_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L Wang","year":"1994","unstructured":"Wang L, Jiang T: On the complexity of multiple sequence alignment. J Comp Biol. 1994, 1: 337-348.","journal-title":"J Comp Biol"},{"key":"1512_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G: Biological Sequence Analysis. 1998, Cambridge: Cambridge University Press"},{"key":"1512_CR12","volume-title":"Molecular Phylogeny Reconstruction","author":"S Kumar","year":"2000","unstructured":"Kumar S, Filipski AJ: Molecular Phylogeny Reconstruction. 2000, Oxford University Press"},{"key":"1512_CR13","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.pt.2003.10.004","volume":"19","author":"JR Stevens","year":"2003","unstructured":"Stevens JR, Schofield CJ: Phylogenetics and sequence analysis \u2013 some problems for the unwary. Trends in Parasitology. 2003, 19: 582-588.","journal-title":"Trends in Parasitology"},{"key":"1512_CR14","doi-asserted-by":"publisher","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","volume":"27","author":"JD Thompson","year":"1999","unstructured":"Thompson JD, Plewniak F, Poch O: A comprehensive comparison of multiple sequence alignment programs. Nucleic Acids Res. 1999, 27: 2682-2690.","journal-title":"Nucleic Acids Res"},{"key":"1512_CR15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.sbi.2005.04.002","volume":"15","author":"IM Wallace","year":"2005","unstructured":"Wallace IM, Blackshields G, Higgins DG: Multiple sequence alignments. Curr Opin Struct Biol. 2005, 15: 261-266.","journal-title":"Curr Opin Struct Biol"},{"key":"1512_CR16","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"DF Feng","year":"1987","unstructured":"Feng DF, Doolittle RF: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J Mol Evol. 1987, 25: 351-360.","journal-title":"J Mol Evol"},{"key":"1512_CR17","unstructured":"Kumar S, Filipski AJ: Multiple Sequence Alignment: In Pursuit of Homologous DNA Positions. Genome Res."},{"key":"1512_CR18","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1089\/cmb.1995.2.459","volume":"2","author":"SK Gupta","year":"1995","unstructured":"Gupta SK, Kececioglu JD, Schaffer AA: Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment. J Comput Biol. 1995, 2: 459-72.","journal-title":"J Comput Biol"},{"key":"1512_CR19","doi-asserted-by":"publisher","first-page":"1552","DOI":"10.1137\/0149094","volume":"49","author":"JL Spouge","year":"1989","unstructured":"Spouge JL: Speeding up dynamic programming algorithms for finding optimal latticepaths. SIAM J Appl Math. 1989, 49: 1552-1566.","journal-title":"SIAM J Appl Math"},{"key":"1512_CR20","volume-title":"CRC Handbook of Combinatorial Designs","year":"1996","unstructured":"Colbourn CJ, Dinitz J, (Eds): CRC Handbook of Combinatorial Designs. 1996, Boca Raton FL: CRC Press"},{"key":"1512_CR21","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198535768.001.0001","volume-title":"Triple Systems","author":"CJ Colbourn","year":"1999","unstructured":"Colbourn CJ, Rosa A: Triple Systems. 1999, Oxford: Oxford University Press"},{"issue":"4","key":"1512_CR22","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I: The NP-completeness of some edge-partition problems. SIAM J Comput. 1981, 10 (4): 713-717.","journal-title":"SIAM J Comput"},{"key":"1512_CR23","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1186\/1471-2105-6-278","volume":"6","author":"MS Rosenberg","year":"2005","unstructured":"Rosenberg MS: Multiple sequence alignment accuracy and evolutionary distance estimation. BMC Bioinformatics. 2005, 6: 278-","journal-title":"BMC Bioinformatics"},{"key":"1512_CR24","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0012-365X(85)90116-5","volume":"26","author":"DR Stinson","year":"1985","unstructured":"Stinson DR: Hill-climbing algorithms for the construction of combinatorial designs. Annals Discrete Math. 1985, 26: 321-334.","journal-title":"Annals Discrete Math"},{"key":"1512_CR25","first-page":"718","volume-title":"CRC Handbook of Combinatorial Designs","author":"PB Gibbons","year":"1996","unstructured":"Gibbons PB: Computational Methods in Design Theory. CRC Handbook of Combinatorial Designs. 1996, Boca Raton FL: CRC Press, 718-740."},{"key":"1512_CR26","first-page":"13","volume":"2","author":"CJ Colbourn","year":"1987","unstructured":"Colbourn CJ, Mathon R: Leave graphs of small maximal partial triple systems. J Combin Math Combin Comput. 1987, 2: 13-28.","journal-title":"J Combin Math Combin Comput"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-140.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-8-140\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-8-140.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T00:59:46Z","timestamp":1707872386000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-8-140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4,30]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["1512"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-8-140","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,4,30]]},"article-number":"140"}}