{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:58:35Z","timestamp":1725559115043},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540258667"},{"type":"electronic","value":"9783540319504"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11415770_16","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T03:44:50Z","timestamp":1278992690000},"page":"204-216","source":"Crossref","is-referenced-by-count":2,"title":["A Polynomial Time Solvable Formulation of Multiple Sequence Alignment"],"prefix":"10.1007","author":[{"given":"Sing-Hoi","family":"Sze","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yue","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingwu","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1137\/0149012","volume":"49","author":"S.F. Altschul","year":"1989","unstructured":"Altschul, S.F., Lipman, D.J.: Trees, stars, and multiple biological sequence alignment. SIAM J. Appl. Math.\u00a049, 197\u2013209 (1989)","journal-title":"SIAM J. Appl. Math."},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H. Carillo","year":"1988","unstructured":"Carillo, H., Lipman, D.: The multiple sequence alignment problem in biology. SIAM J. Appl. Math.\u00a048, 1073\u20131082 (1988)","journal-title":"SIAM J. Appl. Math."},{"key":"16_CR3","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"16_CR4","unstructured":"Do, C., Brudno, M., Batzoglou, S.: PROBCONS: probabilistic consistency-based multiple alignment of amino acid sequences. In: Proc. 12th Int. Conf. Intelligent Systems Mol. Biol.\/3rd European Conf. Comp. Biol, ISMB\/ECCB 2004 (2004)"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"R.C. Edgar","year":"2004","unstructured":"Edgar, R.C.: MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res.\u00a032, 1792\u20131797 (2004)","journal-title":"Nucleic Acids Res."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"D. Feng","year":"1987","unstructured":"Feng, D., Doolittle, R.: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Mol. Evol.\u00a025, 351\u2013360 (1987)","journal-title":"J. Mol. Evol."},{"key":"16_CR7","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/BF02462264","volume":"52","author":"O. Gotoh","year":"1990","unstructured":"Gotoh, O.: Consistency of optimal sequence alignments. Bull. Math. Biol.\u00a052, 509\u2013525 (1990)","journal-title":"Bull. Math. Biol."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1006\/jmbi.1996.0679","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. Biol.\u00a0264, 823\u2013838 (1996)","journal-title":"J. Mol. Biol."},{"key":"16_CR9","doi-asserted-by":"crossref","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. Bull. Math. Biol.\u00a055, 141\u2013154 (1993)","journal-title":"Bull. Math. Biol."},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Heger, A., Lappe, M., Holm, L.: Accurate detection of very sparse sequence motifs. In: Proc. 7th Ann. Int. Conf. Res. Comp. Mol. Biol (RECOMB 2003), pp. 139\u2013147 (2003)","DOI":"10.1145\/640075.640094"},{"key":"16_CR11","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 with SP-score. J. Comp. Biol.\u00a08, 615\u2013623 (2001)","journal-title":"J. Comp. Biol."},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/BFb0029800","volume-title":"The maximum weight trace problem in multiple sequence alignment","author":"J.D. Kececioglu","year":"1993","unstructured":"Kececioglu, J.D.: The maximum weight trace problem in multiple sequence alignment. LNCS, vol.\u00a0684, pp. 106\u2013119. Springer, Heidelberg (1993)"},{"key":"16_CR13","series-title":"Fundamental Algorithms","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1997","unstructured":"Knuth, D.E.: The Art of Computer Programming, 3rd edn. Fundamental Algorithms, vol.\u00a01. Addison-Wesley, Reading (1997)","edition":"3"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","volume":"18","author":"C. Lee","year":"2002","unstructured":"Lee, C., Grasso, C., Sharlow, M.F.: Multiple sequence alignment using partial order graphs. Bioinformatics\u00a018, 452\u2013464 (2002)","journal-title":"Bioinformatics"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"12098","DOI":"10.1073\/pnas.93.22.12098","volume":"93","author":"B. Morgenstern","year":"1996","unstructured":"Morgenstern, B., Dress, A., Werner, T.: Multiple DNA and protein sequence alignment based on segment-to-segment comparison. Proc. Natl. Acad. Sci. USA\u00a093, 12098\u201312103 (1996)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/0020-7519(96)00044-6","volume":"26","author":"D.A. Morrison","year":"1996","unstructured":"Morrison, D.A.: Phylogenetic tree-building. Int. J. Parasitology\u00a026, 589\u2013617 (1996)","journal-title":"Int. J. Parasitology"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S.B. Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol.\u00a048, 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C. Notredame","year":"2000","unstructured":"Notredame, C., Higgins, D.G., Heringa, J.: T-Coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol.\u00a0302, 205\u2013217 (2000)","journal-title":"J. Mol. Biol."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1093\/bioinformatics\/14.5.407","volume":"14","author":"C. Notredame","year":"1998","unstructured":"Notredame, C., Holm, L., Higgins, D.G.: COFFEE: an objective function for multiple sequence alignments. Bioinformatics\u00a014, 407\u2013422 (1998)","journal-title":"Bioinformatics"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.jmb.2004.04.058","volume":"340","author":"O. O\u2019Sullivan","year":"2004","unstructured":"O\u2019Sullivan, O., Suhre, K., Abergel, C., Higgins, D.G., Notredame, C.: 3DCoffee: combining protein sequences and structures within multiple sequence alignments. J. Mol. Biol.\u00a0340, 385\u2013395 (2004)","journal-title":"J. Mol. Biol."},{"key":"16_CR21","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology: an Algorithmic Approach","author":"P.A. Pevzner","year":"2000","unstructured":"Pevzner, P.A.: Computational Molecular Biology: an Algorithmic Approach. MIT Press, Cambridge (2000)"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T.F. Smith","year":"1981","unstructured":"Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences. J. Mol. Biol.\u00a0147, 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0378-1119(98)00097-3","volume":"211","author":"J. Stoye","year":"1998","unstructured":"Stoye, J.: Multiple sequence alignment with the divide-and-conquer method. Gene\u00a0211, GC45\u2013GC56 (1998)","journal-title":"Gene"},{"key":"16_CR24","first-page":"81","volume":"3","author":"W.R. Taylor","year":"1987","unstructured":"Taylor, W.R.: Multiple sequence alignment by a pairwise algorithm. Comp. Appl. Biosci.\u00a03, 81\u201387 (1987)","journal-title":"Comp. Appl. Biosci."},{"key":"16_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF02143508","volume":"28","author":"W.R. Taylor","year":"1988","unstructured":"Taylor, W.R.: A flexible method to align large numbers of biological sequences. J. Mol. Evol.\u00a028, 161\u2013169 (1988)","journal-title":"J. Mol. Evol."},{"key":"16_CR26","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"J.D. Thompson","year":"1994","unstructured":"Thompson, J.D., Higgins, D.G., Gibson, T.J.: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice. Nucleic Acids Res.\u00a022, 4673\u20134680 (1994)","journal-title":"Nucleic Acids Res."},{"key":"16_CR27","doi-asserted-by":"publisher","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","volume":"27","author":"J.D. Thompson","year":"1999","unstructured":"Thompson, J.D., Plewniak, F., Poch, O.: A comprehensive comparison of multiple sequence alignment programs. Nucleic Acids Res.\u00a027, 2682\u20132690 (1999)","journal-title":"Nucleic Acids Res."},{"key":"16_CR28","doi-asserted-by":"publisher","first-page":"1428","DOI":"10.1093\/bioinformatics\/bth116","volume":"20","author":"I. Walle Van","year":"2004","unstructured":"Van Walle, I., Lasters, I., Wyns, L.: Align-m \u2014 a new algorithm for multiple alignment of highly divergent sequences. Bioinformatics\u00a020, 1428\u20131435 (2004)","journal-title":"Bioinformatics"},{"key":"16_CR29","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0022-2836(91)90871-3","volume":"218","author":"M. Vingron","year":"1991","unstructured":"Vingron, M., Argos, P.: Motif recognition and alignment for many sequences by comparison of dot-matrices. J. Mol. Biol.\u00a0218, 33\u201343 (1991)","journal-title":"J. Mol. Biol."},{"key":"16_CR30","doi-asserted-by":"publisher","first-page":"119","DOI":"10.2307\/3001946","volume":"3","author":"F. Wilcoxon","year":"1947","unstructured":"Wilcoxon, F.: Probability tables for individual comparisons by ranking methods. Biometrics\u00a03, 119\u2013122 (1947)","journal-title":"Biometrics"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11415770_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T19:55:57Z","timestamp":1558295757000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11415770_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540258667","9783540319504"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/11415770_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}