On reconstructing species trees from gene trees in term of duplications and losses

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On reconstructing species trees from gene trees in term of duplications and losses

Full text

Pdf (1.17 MB)

Source

Annual Conference on Research in Computational Molecular Biology archive
Proceedings of the second annual international conference on Computational molecular biology table of contents

New York, New York, United States

Pages: 182 - 191

Year of Publication: 1998

ISBN:0-89791-976-9

Authors

Bin Ma	Dept. of Mathematics, Peking University, Beijing 100871, P. R. of China
Ming Li	Dept. of Computer Science, University of Waterloo, Canada N2L 3G1
Louxin Zhang	BioInfonnatics Center & ISS, National University of Singapore, Singapore 119597

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 16, Citation Count: 4

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/279069.279113 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	B. DasGupta , X. He , T. Jiang , M. Li , J. Tromp , L. Zhang, On distances between phylogenetic trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.427-436, January 05-07, 1997, New Orleans, Louisiana, United States
	3	O. Eulenstein and M. Vingron, On the equivalence of two tree mapping measures, Arbeitspapiere der GMD, 936, Bonn, Germany.
	4	O. Eulenstein, B. 5~rkin and M. Vingron, Duplication-based measures of difference between gene and species trees, to appear on or. Comput. Biology.
	5	Martin Farach , Mikkel Thorup, Fast comparison of evolutionary trees, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.481-488, January 23-25, 1994, Arlington, Virginia, United States
	6	J. Felsenstein, Phylogenies from molecular sequences: Inference and reliability, Ann. Review Genet. 22(1988), 521-561.
	7	W. Fitch, Distinguishing homologous and analogous proteins, Syst. 2ool. 19(1970), 99-113.
	8	~V. Fitch and E. Margoliash, Construction of phylogenetic trees, Science 155(1967), 279-284.
	9	Z. Ga}i! and N. Megiddo, Cyclic ordering is NP- Complete, Theoret. Comput. Sci. 5(1977), 179-182.
	10	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	11	M. Goodman, J. Czelusniak, G.W. Moore, A.E. Romero-Herrera and G. Matsuda, Fitting the gene lineage into its species lineage. A parsimony strategy illustrated by cladograms constructed from globin sequences, Syst. Zool. 28(1979), 132-163.
	12	P~ Guig6, I. Muchnik and T. Smith, Reconstruction of ancient molecular phylogeny, Molecular Phylogenetics and Evolution 6(1996), No. 2, 189- 213.
	13	B. Mirkin, I. Muchnik and T. Smith, A biologically meanJng~ model for comparing molecular phylogenies, J. Gomput. Biology 2(1995), 493-507.
	14	G. W. Moore, M. Goodman and J. Barnabas, An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posed by molecular data sets, J. Theoret. Biol. 38(1973), 423-457.
	15	M. Net, Molecular Evolutionary Genetics. Coltunbia University Press, New York, 1987.
	16	J. E. Neigel and J. C. Avise, Phylogenetic relationship of mitochondrial DNA under various demographic models of speciation, Evolutionary Processes and Theory, 515-534, Academic Press, New York, 1986.
	17	S. Ohno, Evolution by gene duplication. Springer- Verlag, Berlin, 1970.
	18	R.D.M. Page, Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas, Syst. Biol. 43(1994), 58-77.
	19	R.D.M. Page and M. Charleston, From gene to orgaulsmal phylogeny: reconciled trees and the gene tree/species tree problem, Molecular Phylogenetics and Evolution 7(1997), 231-240.
	20	P. Pamilo and M. Net, Relationship between gene trees and species trees. Mol. Bio. Evol. 5 (1988), 568-583.
	21	M. Steel, The complexity of reconstructing trees from qualitative characters and subtrees, J. Classifications 9(1992), 91-116.
	22	D. Swofford and G. Olsen, Phylogeny reconstruction. In Molecular Systematics(edited by D. M. l:{illis et al.), Sinauer Associates, Sunderland, 411- 501.
	23	N. Takahata, Gene genealogy in three related population: Consistency probability between gene and population trees, Genetics 122(1989), 957-966.
	24	M. Waterman and T. Smith, On the similarity of dendrograms, J. Theoret. Biol. 73(1978), 789-800.
	25	L. Zhang, On a Mirkin-Muchnik-Smith conjecture for comparing molecular phylogenies, Y. Gomput. B~ology 4(1997), 17?4Ss.

CITED BY 4

	M. T. Hallett , J. Lagergren, New algorithms for the duplication-loss model, Proceedings of the fourth annual international conference on Computational molecular biology, p.138-146, April 2000, Tokyo, Japan
	Pawel Górecki, Reconciliation problems for duplication, loss and horizontal gene transfer, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.316-325, March 27-31, 2004, San Diego, California, USA
	Paweł Górecki , Jerzy Tiuryn, DLS-trees: a model of evolutionary scenarios, Theoretical Computer Science, v.359 n.1, p.378-399, 14 August 2006
	Mukul S. Bansal , Oliver Eulenstein, An Ω(n^2/ log n) Speed-Up of TBR Heuristics for the Gene-Duplication Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.4, p.514-524, October 2008