{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:35:50Z","timestamp":1725561350018},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206958"},{"type":"electronic","value":"9783540245872"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24587-2_36","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T04:59:19Z","timestamp":1280379559000},"page":"339-351","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome"],"prefix":"10.1007","author":[{"given":"Yaw-Ling","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsan-Sheng","family":"Hsu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"36_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A.V. Aho","year":"1981","unstructured":"Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing\u00a010(3), 405\u2013421 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"B.L. Allen","year":"2001","unstructured":"Allen, B.L., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics\u00a05, 1\u201313 (2001)","journal-title":"Annals of Combinatorics"},{"issue":"6","key":"36_CR3","doi-asserted-by":"publisher","first-page":"1656","DOI":"10.1137\/S0097539794269461","volume":"26","author":"A. Amir","year":"1997","unstructured":"Amir, A., Keselman, D.: Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. SIAM Journal on Computing\u00a026(6), 1656\u20131669 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"36_CR4","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0304-3975(99)00235-2","volume":"240","author":"V. Berry","year":"2000","unstructured":"Berry, V., Gascuel, O.: Inferring evolutionary trees with strong combinatorial evidence. Theoretical Computer Science\u00a0240(2), 271\u2013298 (2000)","journal-title":"Theoretical Computer Science"},{"key":"36_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-45123-4_12","volume-title":"Combinatorial Pattern Matching","author":"P. Bonizzoni","year":"2000","unstructured":"Bonizzoni, P., Della Vedova, G., Mauri, G.: Approximating the maximum isomorphic agreement subtree is hard. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 119\u2013128. Springer, Heidelberg (2000)"},{"key":"36_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/3-540-45678-3_62","volume-title":"Algorithms and Computation","author":"G.S. Brodal","year":"2001","unstructured":"Brodal, G.S., Fagerberg, R., Pedersen, C.N.: Computing the quartet distance between evolutionary trees in time O(n log 2 n). In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 731\u2013742. Springer, Heidelberg (2001)"},{"key":"36_CR7","unstructured":"Bryant, D.: Building Trees, Hunting for Trees, and Comparing Trees. PhD thesis, University of Canterbury, Christchurch, New Zealand (1997)"},{"issue":"5","key":"36_CR8","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1137\/S0097539796313477","volume":"30","author":"R. Cole","year":"2002","unstructured":"Cole, R., Farach, M., Hariharan, R., Przytycka, T., Thorup, M.: An O(n log n) algorithm for the maximum agreement subtree problem for binary trees. SIAM Journal on Computing\u00a030(5), 1385\u20131404 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR9","unstructured":"DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Zhang, L.: On distances between phylogenetic trees. In: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 427\u2013436 (1997)"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01908061","volume":"2","author":"W.H.E. Day","year":"1985","unstructured":"Day, W.H.E.: Optimal algorithms for comparing trees with labelled leaves. Journal of Classification\u00a02, 7\u201328 (1985)","journal-title":"Journal of Classification"},{"issue":"2","key":"36_CR11","doi-asserted-by":"publisher","first-page":"193","DOI":"10.2307\/2413326","volume":"34","author":"G. Estabrook","year":"1985","unstructured":"Estabrook, G., McMorris, F., Meacham, C.: Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units. Systematic Zoology\u00a034(2), 193\u2013200 (1985)","journal-title":"Systematic Zoology"},{"issue":"6","key":"36_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","volume":"55","author":"M. Farach","year":"1995","unstructured":"Farach, M., Przytycka, T.M., Thorup, M.: On the agreement of many trees. Information Processing Letters\u00a055(6), 297\u2013301 (1995)","journal-title":"Information Processing Letters"},{"issue":"1","key":"36_CR13","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794262422","volume":"26","author":"M. Farach","year":"1997","unstructured":"Farach, M., Thorup, M.: Sparse dynamic programming for evolutionary-tree comparison. SIAM Journal on Computing\u00a026(1), 210\u2013230 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"36_CR14","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1086\/412935","volume":"57","author":"J. Felsenstein","year":"1982","unstructured":"Felsenstein, J.: Numerical methods for inferring evolutionary trees. Quarterly Review on Biology\u00a057(4), 379\u2013404 (1982)","journal-title":"Quarterly Review on Biology"},{"key":"36_CR15","doi-asserted-by":"publisher","first-page":"406","DOI":"10.2307\/2412116","volume":"20","author":"W.M. Fitch","year":"1971","unstructured":"Fitch, W.M.: Toward defining the course of evolution: Minimal change for a specific tree topology. Systematic Zoology\u00a020, 406\u2013441 (1971)","journal-title":"Systematic Zoology"},{"key":"36_CR16","doi-asserted-by":"crossref","unstructured":"Gilbert, D., Westhead, D., Nagano, N., Thornton, J.: Motif\u2013based searching in tops protein topology databases (1999)","DOI":"10.1093\/bioinformatics\/15.4.317"},{"key":"36_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks\u00a021, 19\u201328 (1991)","journal-title":"Networks"},{"issue":"2","key":"36_CR18","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","volume":"71","author":"J. Hein","year":"1996","unstructured":"Hein, J., Jiang, T., Wang, L., Zhang, K.: On the complexity of comparing evolutionary trees. Discrete Applied Mathematics\u00a071, 153\u2013169 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"36_CR20","doi-asserted-by":"crossref","DOI":"10.1128\/9781555818319","volume-title":"Two-Component Signal Transduction","author":"J.A. Hoch","year":"1995","unstructured":"Hoch, J.A., Silhavy, T.J.: Two-Component Signal Transduction. ASM Press, Washington (1995)"},{"key":"36_CR21","unstructured":"Lin, Y.L.: Two component systems sequence characteristics identification in bacterial genome. In: Sixth Proceedings World Multiconference on Systemics, Cybernetics and Informatics (SCI 2002), pp. 445\u2013449, Orlando, Florida (2002)"},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1146\/annurev.ge.26.120192.000443","volume":"26","author":"J.S. Parkinson","year":"1992","unstructured":"Parkinson, J.S., Kofoid, E.C.: Communication modules in bacterial signalling proteins. Annu. Rev. Genet.\u00a026, 71\u2013112 (1992)","journal-title":"Annu. Rev. Genet."},{"key":"36_CR23","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BFb0102690","volume-title":"Combinatorial mathematics, VI, Proc. Sixth Austral. Conf","author":"D.F. Robinson","year":"1979","unstructured":"Robinson, D.F., Foulds, L.R.: Comparison of weighted labelled trees. In: Combinatorial mathematics, VI, Proc. Sixth Austral. Conf. Lecture Notes in Mathematics, vol.\u00a0748, pp. 119\u2013126. Springer, Berlin (1979)"},{"issue":"1-2","key":"36_CR24","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"D.F. Robinson","year":"1981","unstructured":"Robinson, D.F., Foulds, L.R.: Comparison of phylogenetic trees. Math. Biosci\u00a053(1-2), 131\u2013147 (1981)","journal-title":"Math. Biosci"},{"key":"36_CR25","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0966-842X(00)01833-3","volume":"8","author":"A. Rodrigue","year":"2000","unstructured":"Rodrigue, A., Quentin, Y., Lazdunski, A., M\u00e9jean, V., Foglino, M.: Twocomponent systems in pseudomonas aeruginosa: why so many? Trends Microbiol\u00a08, 498\u2013504 (2000)","journal-title":"Trends Microbiol"},{"key":"36_CR26","first-page":"406","volume":"4","author":"N. Saitou","year":"1987","unstructured":"Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology Evolution\u00a04, 406\u2013425 (1987)","journal-title":"Molecular Biology Evolution"},{"issue":"7","key":"36_CR27","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1093\/oxfordjournals.molbev.a025664","volume":"13","author":"K. Strimmer","year":"1996","unstructured":"Strimmer, K., von Haeseler, A.: Quartet puzzling: a quartet maximum-likelihood method for reconstructing tree topologies. Molecular Biology and Evolution\u00a013(7), 964\u2013969 (1996)","journal-title":"Molecular Biology and Evolution"},{"key":"36_CR28","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"key":"36_CR29","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/0022-5193(78)90137-6","volume":"73","author":"M.S. Waterman","year":"1978","unstructured":"Waterman, M.S., Smith, T.F.: On the similarity of dendrograms. Journal of Theoretical Biology\u00a073, 789\u2013800 (1978)","journal-title":"Journal of Theoretical Biology"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24587-2_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:55:43Z","timestamp":1559332543000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24587-2_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206958","9783540245872"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24587-2_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}