{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T00:10:10Z","timestamp":1742602210639,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632207"},{"type":"electronic","value":"9783540692140"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63220-4_58","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:18:27Z","timestamp":1330298307000},"page":"167-179","source":"Crossref","is-referenced-by-count":7,"title":["On incremental computation of transitive closure and greedy alignment"],"prefix":"10.1007","author":[{"given":"Sa\u00efd","family":"Abdedda\u00efm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"14_CR1","unstructured":"M. R. Garey and D. S. Johnson. Computers and intractability; a guide to the theory of NP-completeness. Freeman, 1979."},{"key":"14_CR2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L. Wang","year":"1994","unstructured":"L. Wang and T. Jiang. On the complexity of multiple sequence alignment. J. Comput. Biol., 1:337\u2013348, 1994.","journal-title":"J. Comput. Biol."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"T. Jiang, E. L. Lawler, and L. Wang. Aligning sequences via an evolutionary tree: complexity and approximation. In Proc. 26-th Annual ACM Symp. Theory of Comput., pages 760\u2013769, 1994.","DOI":"10.1145\/195058.195454"},{"key":"14_CR4","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02257378","volume":"20","author":"P. Hogeweg","year":"1984","unstructured":"P. Hogeweg and B. Hesper. The alignment of sets of sequences and the construction of phyletic trees: an integrated method. J. Mol. Evol., 20:175\u2013186, 1984.","journal-title":"J. Mol. Evol."},{"key":"14_CR5","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"D-F. Feng","year":"1987","unstructured":"D-F. Feng and R. F. Doolittle. Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Mol. Evol., 25:351\u2013360, 1987.","journal-title":"J. Mol. Evol."},{"key":"14_CR6","unstructured":"W. R. Taylor. Protein structure prediction. In M. J. Bishop and C. J. Rawlings, editors, Nucleic Acid and Protein Sequence Analysis, a Practical Approach., pages 285\u2013323. IRL Press, 1987."},{"issue":"22","key":"14_CR7","doi-asserted-by":"crossref","first-page":"10881","DOI":"10.1093\/nar\/16.22.10881","volume":"16","author":"F. Corpet","year":"1988","unstructured":"F. Corpet. Multiple sequence alignment with hierarchial clustering. Nucleic Acids Research, 16(22): 10881\u201310890, 1988.","journal-title":"Nucleic Acids Research"},{"key":"14_CR8","first-page":"151","volume":"5","author":"D.G. Higgins","year":"1989","unstructured":"D.G. Higgins and P.M. Sharp. Fast and sensitive multiple sequence alignments on a microcomputer. CABIOS, 5:151\u2013153, 1989.","journal-title":"CABIOS"},{"issue":"4","key":"14_CR9","first-page":"379","volume":"10","author":"O. Gotoh","year":"1994","unstructured":"O. Gotoh. Further improvement in methods of group-to-group sequence alignment with generalized profile operations. CABIOS, 10(4):379\u2013387, 1994.","journal-title":"CABIOS"},{"key":"14_CR10","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1109\/34.31450","volume":"11","author":"A. M. Landraud","year":"1989","unstructured":"A. M. Landraud, J. F. Avril, and P. Chr\u00e9tienne. An algorithm for finding a common structure shared by a family of strings. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:890\u2013895, 1989.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Said Abdeddaim. Fast and sound two-step algorithms for multiple alignment of nucleic sequences. In Proceedings of the IEEE International Joint Symposia on Intelligence and Systems, pages 4\u201311, 1996.","DOI":"10.1109\/IJSIS.1996.565044"},{"key":"14_CR12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0190(83)90033-9","volume":"16","author":"T. Ibaraki","year":"1983","unstructured":"T. Ibaraki and N. Katoh. On-line computation of transitive closure for graphs. Inform. Proc. Lett., 16:95\u201397, 1983.","journal-title":"Inform. Proc. Lett."},{"key":"14_CR13","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(86)90098-8","volume":"48","author":"G. F. Italiano","year":"1986","unstructured":"G. F. Italiano. Amortized efficiency of a path retrieval data structure. Theor. Comput. Sci., 48:273\u2013281, 1986.","journal-title":"Theor. Comput. Sci."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"J. A. La Poutr\u00e9 and J. van Leeuwen. Maintenance of transitive closure and transitive reduction of graphs. In Proc. Workshop on Graph-Theoretic Concepts in Computer Science, pages 106\u2013120. Lecture Notes in Computer Science 314, Springer-Verlag, 1988.","DOI":"10.1007\/3-540-19422-3_9"},{"key":"14_CR15","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"J. D. Thompson","year":"1994","unstructured":"J. D. Thompson, D. G. Higgins, and T. J. Gibson. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice. Nucleic Acids Research, 22:4673\u20134680, 1994.","journal-title":"Nucleic Acids Research"},{"key":"14_CR16","unstructured":"F. Mattern. Virtual time and global states of distributed systems. In Proc. Workshop on Parallel and Distributed Algorithms, pages 215\u2013226, 1989."},{"key":"14_CR17","unstructured":"C. J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. In 11-th Australian Computer Science Conference, pages 55\u201366, 1988."},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"J. Kececioglu. The maximum weight trace problem in multiple sequence alignment. In 4-th Annual Symp. Combinatorial Pattern Matching, volume 684 of LNCS, pages 106\u2013119. 1993.","DOI":"10.1007\/BFb0029800"},{"key":"14_CR19","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/S0022-5193(89)80196-1","volume":"138","author":"S. F. Altschul","year":"1989","unstructured":"S. F. Altschul. Gap costs for multiple sequence alignment. J. Theor. Biol., 138:297\u2013309, 1989.","journal-title":"J. Theor. Biol."},{"key":"14_CR20","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T. F. Smith","year":"1981","unstructured":"T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. J. Mol. Biol., 147:195\u2013197, 1981.","journal-title":"J. Mol. Biol."},{"key":"14_CR21","first-page":"3590","volume":"22","author":"T. K. Attwood","year":"1994","unstructured":"T. K. Attwood, M. E. Beck, A. J. Bleasby, and D. J. Parry-Smith. PRINTS \u2014 a database of protein motif fingeprints. Nucleic Acids Research, 22:3590\u20133596, 1994.","journal-title":"Nucleic Acids Research"},{"key":"14_CR22","unstructured":"M. S. Waterman. Mathematical Methods for DNA Sequences. C.R.C. Press, 1989."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63220-4_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:10Z","timestamp":1742600410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63220-4_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632207","9783540692140"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-63220-4_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}