{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:23Z","timestamp":1763468063496},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540580942"},{"type":"electronic","value":"9783540484509"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58094-8_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:11:47Z","timestamp":1330269107000},"page":"15-30","source":"Crossref","is-referenced-by-count":7,"title":["The parameterized complexity of sequence alignment and consensus"],"prefix":"10.1007","author":[{"given":"Hans","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodney G.","family":"Downey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harold T.","family":"Wareham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"R. A. Baeza-Yates","year":"1991","unstructured":"R. A. Baeza-Yates. Searching subsequences. Theoretical Computer Science 78 (1991), 363\u2013376.","journal-title":"Theoretical Computer Science"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, M. Fellows and M. Hallett. Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy. To appear, Proceedings fo the ACM Symposium on the Theory of Computing, 1994.","DOI":"10.1145\/195058.195229"},{"key":"2_CR3","unstructured":"L. Cai, J. Chen, R. Downey and M. Fellows. The parameterized complexity of short computations and factorization. University of Victoria, Technical Report, Department of Computer Science, July, 1993."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"R. Downey, P. Evans and M. Fellows. Parameterized learning complexity. Proc. Sixth ACM Workshop on Computational Learning Theory (COLT), pp. 51\u201357, ACM Press, 1993.","DOI":"10.1145\/168304.168311"},{"key":"2_CR5","first-page":"36","volume-title":"Fixed-parameter intractability (extended abstract)","author":"R. Downey","year":"1992","unstructured":"R. Downey and M. Fellows. Fixed-parameter intractability (extended abstract). In Proceedings of the Seventh Annual Conference on Structure in Complexity Theory, pp. 36\u201349, IEEE Computer Society Press, Los Alamitos, CA, 1992."},{"key":"2_CR6","volume-title":"Technical Report, Department of Computer Science","author":"R. Downey","year":"1993","unstructured":"R. Downey, M. Fellows, B. Kapron, M. Hallett and H.T. Wareham. The parameterized complexity of some problems in logic and linguistics. Workshop on Recursion Theory and Complexity in Logic, Vancouver, B.C., Canada, October, 1993, and University of Victoria, Technical Report, Department of Computer Science, July, 1993."},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/978-3-642-50974-2_40","volume-title":"Information and Classification \u2014 Concepts, Methods, and Applications","author":"W. H. E. Day","year":"1993","unstructured":"W. H. E. Day and F. R. McMorris. Discovering consensus molecular sequences. In O. Opitz, B. Lausen, and R. Klar (eds.) Information and Classification \u2014 Concepts, Methods, and Applications, pp. 393\u2013402, Springer-Verlag, Berlin, 1993."},{"key":"2_CR8","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0895-7177(93)90117-H","volume":"17","author":"W. H. E. Day","year":"1993","unstructured":"W. H. E. Day and F. R. McMorris. The computation of consensus patterns in DNA sequences. Mathematical and Computer Modelling 17 (1993), 49\u201352.","journal-title":"Mathematical and Computer Modelling"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02460299","volume":"55","author":"D. Gusfield","year":"1993","unstructured":"D. Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin of Mathematical Biology 55 (1993), 141\u2013154.","journal-title":"Bulletin of Mathematical Biology"},{"key":"2_CR10","first-page":"325","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D. S. Hirschberg","year":"1983","unstructured":"D. S. Hirschberg. Recent results on the complexity of common subsequence problems. In D. Sankoff and J. B. Kruskal (eds.) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, pp. 325\u2013330, Addison-Wesley, Reading, MA, 1983."},{"key":"2_CR11","first-page":"214","volume-title":"Lecture Notes in Computer Science no. 644","author":"R. W. Irving","year":"1992","unstructured":"R. W. Irving and C. B. Fraser. Two algorithms for the longest common subsequence of three (or more) strings. In A. Apostolico, M. Crochemore, Z. Galil, and U. Manber (eds.) Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, pp. 214\u2013229, Lecture Notes in Computer Science no. 644, Springer-Verlag, Berlin, 1992."},{"key":"2_CR12","first-page":"265","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"J. B. Kruskal","year":"1983","unstructured":"J. B. Kruskal and D. Sankoff. An anthology of algorithms and concepts for sequence comparison. In D. Sankoff and J. B. Kruskal (eds.) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, pp. 265\u2013310, Addison-Wesley, Reading, MA, 1983."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/TSMC.1978.4309979","volume":"8","author":"S. Y. Lu","year":"1978","unstructured":"S. Y. Lu and K. S. Fu. A sentence-to-sentence clustering procedure for pattern analysis. IEEE Transactions on Systems, Man, and Cybernetics 8 (1978), 381\u2013389.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the ACM 25 (1978), 322\u2013336.","journal-title":"Journal of the ACM"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1016\/0076-6879(92)10029-D","volume":"183","author":"W. R. Pearson","year":"1992","unstructured":"W. R. Pearson and W. Miller. Dynamic programming algorithms for biological sequence comparison. Methods in Enzymology 183 (1992), 575\u2013601.","journal-title":"Methods in Enzymology"},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"1763","DOI":"10.1137\/0152101","volume":"52","author":"P. A. Pevzner","year":"1992","unstructured":"P. A. Pevzner. Multiple alignment, communication cost, and graph matching. SIAM Journal on Applied Mathematics 52 (1992), 1763\u20131779.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D. Sankoff","year":"1972","unstructured":"D. Sankoff. Matching comparisons under deletion\/insertion constraints. PNAS 69 (1972), 4\u20136.","journal-title":"PNAS"},{"key":"2_CR18","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D. Sankoff","year":"1985","unstructured":"D. Sankoff. Simultaneous solution of the RNA folding, alignment, and protosequence problems. SIAM Journal on Applied Mathematics 45 (1985), 810\u2013825.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"2_CR19","unstructured":"H. T. Wareham. On the Computational Complexity of Inferring Evolutionary Trees, M.Sc. Thesis, Technical Report no. 9301, Department of Computer Science, Memorial University of Newfoundland, 1993."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58094-8_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:16:55Z","timestamp":1605647815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58094-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580942","9783540484509"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-58094-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}