{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T05:41:59Z","timestamp":1742967719236,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020070"},{"type":"electronic","value":"9783642020087"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02008-7_32","type":"book-chapter","created":{"date-parts":[[2009,5,13]],"date-time":"2009-05-13T17:28:14Z","timestamp":1242235694000},"page":"451-465","source":"Crossref","is-referenced-by-count":12,"title":["Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep"],"prefix":"10.1007","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[]},{"given":"Elchanan","family":"Mossel","sequence":"additional","affiliation":[]},{"given":"Sebastien","family":"Roch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"32_CR1","volume-title":"Inferring Phylogenies","author":"J. Felsenstein","year":"2004","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer, Sunderland (2004)"},{"key":"32_CR2","series-title":"Mathematics and its Applications series","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Mathematics and its Applications series, vol.\u00a022. Oxford University Press, Oxford (2003)"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0025-5564(82)90125-0","volume":"60","author":"R.L. Graham","year":"1982","unstructured":"Graham, R.L., Foulds, L.R.: Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time. Math. Biosci.\u00a060, 133\u2013142 (1982)","journal-title":"Math. Biosci."},{"issue":"2","key":"32_CR4","doi-asserted-by":"publisher","first-page":"224","DOI":"10.2307\/2413432","volume":"35","author":"W.H.E. Day","year":"1986","unstructured":"Day, W.H.E., Sankoff, D.: Computational complexity of inferring phylogenies by compatibility. Syst. Zool.\u00a035(2), 224\u2013229 (1986)","journal-title":"Syst. Zool."},{"issue":"4","key":"32_CR5","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF02458863","volume":"49","author":"W.H.E. Day","year":"1987","unstructured":"Day, W.H.E.: Computational complexity of inferring phylogenies from dissimilarity matrices. Bull. Math. Biol.\u00a049(4), 461\u2013467 (1987)","journal-title":"Bull. Math. Biol."},{"issue":"5","key":"32_CR6","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1145\/1183907.1183909","volume":"53","author":"B. Chor","year":"2006","unstructured":"Chor, B., Tuller, T.: Finding a maximum likelihood tree is hard. J. ACM\u00a053(5), 722\u2013744 (2006)","journal-title":"J. ACM"},{"issue":"1","key":"32_CR7","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1109\/TCBB.2006.4","volume":"3","author":"S. Roch","year":"2006","unstructured":"Roch, S.: A short proof that phylogenetic tree reconstruction by maximum likelihood is hard. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a03(1), 92\u201394 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Felsenstein, J.: Cases in which parsimony or compatibility methods will be positively misleading. Syst. Biol., 401\u2013410 (1978)","DOI":"10.1093\/sysbio\/27.4.401"},{"issue":"2-3","key":"32_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/PL00008277","volume":"25","author":"K. Atteson","year":"1999","unstructured":"Atteson, K.: The performance of neighbor-joining methods of phylogenetic reconstruction. Algorithmica\u00a025(2-3), 251\u2013278 (1999)","journal-title":"Algorithmica"},{"issue":"2","key":"32_CR10","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.mbs.2005.11.003","volume":"199","author":"M.R. Lacey","year":"2006","unstructured":"Lacey, M.R., Chang, J.T.: A signal-to-noise analysis of phylogeny estimation by neighbor-joining: insufficiency of polynomial length sequences. Math. Biosci.\u00a0199(2), 188\u2013215 (2006)","journal-title":"Math. Biosci."},{"issue":"1","key":"32_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF01609880","volume":"3","author":"M.A. Steel","year":"1999","unstructured":"Steel, M.A., Sz\u00e9kely, L.A.: Inverting random functions. Ann. Comb.\u00a03(1), 103\u2013113 (1999); 3 Combinatorics and biology (Los Alamos, NM, 1998)","journal-title":"Ann. Comb."},{"issue":"4","key":"32_CR12","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1137\/S089548010138790X","volume":"15","author":"M.A. Steel","year":"2002","unstructured":"Steel, M.A., Sz\u00e9kely, L.A.: Inverting random functions. II. Explicit bounds for discrete maximum likelihood estimation, with applications. SIAM J. Discrete Math.\u00a015(4), 562\u2013575 (electronic 2002)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"32_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1002\/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.0.CO;2-R","volume":"14","author":"P.L. Erd\u00f6s","year":"1999","unstructured":"Erd\u00f6s, P.L., Steel, M.A., Sz\u00e9kely, L.A., Warnow, T.A.: A few logs suffice to build (almost) all trees (part 1). Random Struct. Algor.\u00a014(2), 153\u2013184 (1999)","journal-title":"Random Struct. Algor."},{"issue":"4","key":"32_CR14","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. Mol. Biol. Evol.\u00a04(4), 406\u2013425 (1987)","journal-title":"Mol. Biol. Evol."},{"key":"32_CR15","unstructured":"Daskalakis, C., Mossel, E., Roch, S.: Phylogenies without branch bounds: Contracting the short, pruning the deep (2008) (preprint), http:\/\/arxiv.org\/abs\/0801.4190"},{"issue":"1","key":"32_CR16","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0025-5564(96)00075-2","volume":"137","author":"J.T. Chang","year":"1996","unstructured":"Chang, J.T.: Full reconstruction of Markov models on evolutionary trees: identifiability and consistency. Math. Biosci.\u00a0137(1), 51\u201373 (1996)","journal-title":"Math. Biosci."},{"issue":"8","key":"32_CR17","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1016\/S0959-437X(98)80028-2","volume":"8","author":"H. Philippe","year":"1998","unstructured":"Philippe, H., Laurent, J.: How good are deep phylogenetic trees? Current Opinion in Genetics & Development\u00a08(8), 616\u2013623 (1998)","journal-title":"Current Opinion in Genetics & Development"},{"issue":"5765","key":"32_CR18","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1126\/science.1123061","volume":"311","author":"F.D. Ciccarelli","year":"2006","unstructured":"Ciccarelli, F.D., Doerks, T., von Mering, C., Creevey, C.J., Snel, B., Bork, P.: Toward Automatic Reconstruction of a Highly Resolved Tree of Life. Science\u00a0311(5765), 1283\u20131287 (2006)","journal-title":"Science"},{"issue":"1","key":"32_CR19","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/TCBB.2007.1010","volume":"4","author":"E. Mossel","year":"2007","unstructured":"Mossel, E.: Distorted metrics on trees and phylogenetic forests. IEEE\/ACM Trans. Comput. Bio. Bioinform.\u00a04(1), 108\u2013116 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Bio. Bioinform."},{"key":"32_CR20","unstructured":"King, V., Zhang, L., Zhou, Y.: On the complexity of distance-based evolutionary tree reconstruction. In: SODA 2003: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 444\u2013453 (2003)"},{"key":"32_CR21","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/11732990_24","volume-title":"Research in Computational Molecular Biology","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Hill, C., Jaffe, A., Mihaescu, R., Mossel, E., Rao, S.: Maximal accurate forests from distance matrices. In: Apostolico, A., Guerra, C., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2006. LNCS (LNBI), vol.\u00a03909, pp. 281\u2013295. Springer, Heidelberg (2006)"},{"key":"32_CR22","unstructured":"Gronau, I., Moran, S., Snir, S.: Fast and reliable reconstruction of phylogenetic trees with very short edges. To appear in SODA (2008)"},{"key":"32_CR23","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0304-3975(99)00028-6","volume":"221","author":"P.L. Erd\u00f6s","year":"1999","unstructured":"Erd\u00f6s, P.L., Steel, M.A., Sz\u00e9kely, L.A., Warnow, T.A.: A few logs suffice to build (almost) all trees (part 2). Theor. Comput. Sci.\u00a0221, 77\u2013118 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"Huson, D.H., Nettles, S.H., Warnow, T.J.: Disk-covering, a fast-converging method for phylogenetic tree reconstruction. J. Comput. Biol. 6(3-4) (1999)","DOI":"10.1089\/106652799318337"},{"issue":"1","key":"32_CR25","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/S009753970037905X","volume":"31","author":"M. Csur\u00f6s","year":"2001","unstructured":"Csur\u00f6s, M., Kao, M.Y.: Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets. SIAM Journal on Computing\u00a031(1), 306\u2013322 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"32_CR26","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1089\/10665270252935467","volume":"9","author":"M. Csur\u00f6s","year":"2002","unstructured":"Csur\u00f6s, M.: Fast recovery of evolutionary trees with thousands of nodes. J. Comput. Biol.\u00a09(2), 277\u2013297 (2002)","journal-title":"J. Comput. Biol."},{"issue":"2","key":"32_CR27","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1214\/105051606000000024","volume":"16","author":"E. Mossel","year":"2006","unstructured":"Mossel, E., Roch, S.: Learning nonsingular phylogenies and hidden Markov models. Ann. Appl. Probab.\u00a016(2), 583\u2013614 (2006)","journal-title":"Ann. Appl. Probab."},{"key":"32_CR28","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/1132516.1132540","volume-title":"STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Mossel, E., Roch, S.: Optimal phylogenetic reconstruction. In: STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 159\u2013168. ACM Press, New York (2006)"},{"key":"32_CR29","first-page":"187","volume-title":"Mathematics in the Archaelogical and Historical Sciences","author":"P. Buneman","year":"1971","unstructured":"Buneman, P.: The recovery of trees from measures of dissimilarity. In: Mathematics in the Archaelogical and Historical Sciences, pp. 187\u2013395. Edinburgh University Press, Edinburgh (1971)"},{"key":"32_CR30","doi-asserted-by":"publisher","first-page":"591","DOI":"10.2307\/1219940","volume":"30","author":"C.A. Meacham","year":"1981","unstructured":"Meacham, C.A.: A manual method for character compatibility analysis. Taxon\u00a030, 591\u2013600 (1981)","journal-title":"Taxon"},{"issue":"3","key":"32_CR31","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-8858(86)90038-2","volume":"7","author":"H.J. Bandelt","year":"1986","unstructured":"Bandelt, H.J., Dress, A.: Reconstructing the shape of a trea from observed dissimilarity data. Adv. Appl. Math.\u00a07(3), 309\u2013343 (1986)","journal-title":"Adv. Appl. Math."}],"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\/978-3-642-02008-7_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T09:34:40Z","timestamp":1710322480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02008-7_32"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020070","9783642020087"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02008-7_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}