Efficient algorithms for inverting evolution

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient algorithms for inverting evolution

Full text

Pdf (718 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 230 - 236

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Martin Farach	Rutgers University
Sampath Kannan	University of Pennsylvania

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 11, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237814.237868 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Richa Agarwala , Vineet Bafna , Martin Farach , Babu Narayanan , Mike Paterson , Mikkel Thorup, On the approximability of numerical taxonomy (fitting distances by tree metrics), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.365-372, January 28-30, 1996, Atlanta, Georgia, United States
	2	J. Cavender. Taxonomy with confidence. Mathematical Biosciences, 40:271-280, 1978.
	3	W.H.E. Day, D.S. Johnson, and D. Sankoff. The computational complexity of inferring rooted phylogenies by parsimony. Mathematical Biosciences, 81:33-42, 1986.
	4	M. Farach, S. Kannan, and T. Warnow. A l~obust model for finding optimal evolutionary trees. Algorithmica, 13:155-179, 1993.
	5	J. Felsenstein. Cases in which parsimony oc compatibility methods will be positively misleading. Syst. Zool., 22:240-249, 1978.
	6	J. Felsenstein. Numerical methods for infecrinng evolutionary trees. The Quarterly Review of Biology, 57(4), 1982.
	7	J. Felsenstein. Statistical inference of phylogenies. J. R. Statist. Soc. A, 1983.
	8	J. Felsenstein. Phylogenies from molecular sequences: inference and reliability. Annual Review o/ Genetics, 22:521-65, 1988.
	9	R.L. Kashyap and S. Subas. Statistical estimation of parameters in a phylogenetic tree using a dynamic model of the substitutional process. J. theor. Biol., 47:74-101, 1974.
	10	Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, On the learnability of discrete distributions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.273-282, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195155]
	11	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	12	N. Saitou and M. Nei. The neighbor-joining method: a new method for reconstructing phylogentic trees. Mol. Biol. Evol., 4:406-424, 1987.
	13	M. Steel, M.D. Hendy, and D. Penny. A discrete fourier analysis for evolutionary trees. Proceedings of the National Academy of Science, 91:3339-3343, 1994.
	14	D. L. Swofford and G. J. Olsen. Phylogeny reconstruction. In D. M. Hillis and C. Moritz, editors, Molecular Systematics, pages 411-501. Sinauer Associates Inc., Sunderland, MA., 1990.

CITED BY 13

	Paul E. Kearney, The ordinal quartet method, Proceedings of the second annual international conference on Computational molecular biology, p.125-134, March 22-25, 1998, New York, New York, United States
	Daniel H. Huson , Scott Nettles , Tandy J. Warnow, Obtaining highly accurate topology estimates of evolutionary trees from very short sequences, Proceedings of the third annual international conference on Computational molecular biology, p.198-207, April 11-14, 1999, Lyon, France
	Maria Bonet , Mike Steel , Tandy Warnow , Shibu Yooseph, Better methods for solving parsimony and compatibility, Proceedings of the second annual international conference on Computational molecular biology, p.40-49, March 22-25, 1998, New York, New York, United States
	Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Journal of the ACM (JACM), v.46 n.4, p.437-449, July 1999
	Funda Ergün , S. Ravi Kumar , Ronitt Rubinfeld, Learning distributions from random walks, Proceedings of the tenth annual conference on Computational learning theory, p.243-249, July 06-09, 1997, Nashville, Tennessee, United States
	Valerie King , Li Zhang , Yunhong Zhou, On the complexity of distance-based evolutionary tree reconstruction, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Johan Håstad , Lars Ivansson , Jens Lagergren, Fitting points on the real line and its application to RH mapping, Journal of Algorithms, v.49 n.1, p.42-62, 1 October 2003
	Miklós Csűrös , Ming-Yang Kao, Recovering evolutionary trees through harmonic greedy triplets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.261-270, January 17-19, 1999, Baltimore, Maryland, United States
	Mihai Bâdoiu, Approximation algorithm for embedding metrics into a two-dimensional space, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Mihai Bǎdoiu , Erik D. Demaine , Mohammad Taghi Hajiaghayi , Piotr Indyk, Low-dimensional embedding with extra information, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Elchanan Mossel , Sébastien Roch, Learning nonsingular phylogenies and hidden Markov models, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Gagan Aggarwal , Nir Ailon , Florin Constantin , Eyal Even-Dar , Jon Feldman , Gereon Frahling , Monika R. Henzinger , S. Muthukrishnan , Noam Nisan , Martin Pál , Mark Sandler , Anastasios Sidiropoulos, Theory research at Google, ACM SIGACT News, v.39 n.2, June 2008
	Mark Sandler, Hierarchical mixture models: a probabilistic analysis, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA