Probability models for genome rearrangement and linear invariants for phylogenetic inference

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Probability models for genome rearrangement and linear invariants for phylogenetic inference

Full text

Pdf (1.04 MB)

Source

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

Lyon, France

Pages: 302 - 309

Year of Publication: 1999

ISBN:1-58113-069-4

Authors

David Sankoff	Centre de recherches mathématiques, Université de Montréal, CP, 6128 Succursale Centre-ville, Montréal, Québec H3C 3J7
Mathieu Blanchette	Computer Science Department, University of Washington, Seattle, Washington

Sponsors

INRIA : Institut Natl de Recherche en Info et en Automatique
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 32, Citation Count: 3

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/299432.299506 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	Anderson, S., Bankier, A.T., Barrell, B.G., de Bruijn, M.H.L., Coulson, A.R., Drouin, J., Eperon, I.C., Nierlich, D.P., Roe, B.A., Sanger, F., Schreier, P.H., Smith, A.J.H., Staden, R. and Young, I.G. (1981). Sequence and organization of the human mitochondrial genome. Nature 290, 457-465.
	2	Asakawa, S., Himeno, H., Miura, K. and Watanabe, K. (1993). Nucleotide sequence and gene organization of the starfish Asterna pectinifera mitochondrial genome. unpublished.
	3	Vineet Bafna , Pavel Pevzner, Sorting permutations by tanspositions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.614-623, January 22-24, 1995, San Francisco, California, United States
	4	Blanchette, M., Bourque, G. and Sankoff, D. (1997). Breakpoint phylogenies. In: Genome Informatics 1997 (F_~: S. Miyano and T. Takagi) Universal Academy Press, Tokyo, pp. 25-34.
	5	Blanchette, M., Kunisawa, T. and Sankoff, D. (1996). Parametric genome rearrangement. Gene 172, GC 11- 17.
	6	Blanchette, M., Kunisawa, T. and Sankoff, D. (1998). Gene order breakpoint evidence in animal mitochondrial phylogeny, manuscript.
	7	Boore, J.L. and Brown, W.M. (1994). Complete DNA sequence of the mitochondrial genome of the black chiton, Katharina tunicata. Genetics 138, 423-443.
	8	Boore, J.L. and Brown, W.M. (1995). Complete sequence of the mitochondrial DNA of the annelid worm Lumbricus terrestris. Genetics 141, 305-319.
	9	Brusca, R.C. and Brusca, G.J. (1990). Invertebrates. Sinauer, Sunderland, MA.
	10	Bryant, D. (1998). Complexity of the breakpoint median problem. Centre de recherches math6matiques, manuscript.
	11	Alberto Caprara, Sorting by reversals is difficult, Proceedings of the first annual international conference on Computational molecular biology, p.75-83, January 20-23, 1997, Santa Fe, New Mexico, United States [doi>10.1145/267521.267531]
	12	Caprara, A. (1997). Formulations and complexity of multiple sorting by reversals, manuscript, University of Bologna.
	13	Castresana, J., Feldmaier-Fuchs, G. and Paabo, S. (1998). Codon reassignment and amino acid composition in hemichordate mitochondria. Proceedings of the National Academy of Sciences (U.S.A.) 95, 3703-3707.
	14	Cavender, J.A. (1989). M~h~ derivation of linear invariants. Molecular Biology and Evolution 6, 301-316.
	15	Cavender, J.A. and Felsenstein, J. (1987). Invariants of phylogenies: Simple case with discrete states. Journal of Classification 4, 57-71.
	16	Clary, D.O. and Wolstenholme, D.R. (1985). The mitochondrial DNA molecular of Drosophila y~uba: nucleotide sequence, gene organization, and genetic code. Journal of Molecular Evolution 22, 252-271.
	17	Drolet, S. and Sankoff, D. (1990). Quadratic invariants for multivalued characters. Journal of Theoretical Biology 144, ~17-~29.
	18	Eernisse, D.J., Albert,a.s. and Anderson, F.E. (1992). Annelida and Arthropoda are not sister taxa. A phylogenetic analysis of spiralian metazoan morphology. Systematic Biology 41, 305-330.
	19	Evans, S.N. and Speed, T.P. (1993). Invariants of some probability models used in phylogenetic inference. Annals of Statistics 21, 355-377.
	20	Evans, $.N. and Zhou, X. (1998). Constructing and counting phylogenetic invariants. Journal of Computational Biology. to appear.
	21	Felsenstein, J. (1991). Counting phylogenetic invariants in some simple cases. Journal of Theoretical Biology 152, 357-376.
	22	Ferretti, V., Lang, B.F. and Sankoff, D. (1994). Skewed base compositions, asymmetric transition matrices and phylogenetic invariants. Journal of Computational Biology 1, 77-92.
	23	Ferretti, v. and Sankoff, D. (1993). The empirical discovery of phylogenetic invariants. Advances in Applied Probability 25, 290-302.
	24	Ferretti V. and Sankoff D. (1995). Phylogenetic invariants for more general evolutionary models. Journal of Theoretical Biology 173, 147-162.
	25	Ferretti, V. and Sankoff, D. (1996). A remarkable nonlinear invariant for evolution with heterogeneous rates. Mathematical Biociences 134, 71-83.
	26	Fu Y. X. (1995). Linear invariants under Jukes' and Cantor's one-parameter model. Journal of Theoretical Biology 173, 339-352.
	27	Giribet, G. and Ribera, C. (1998). The position of Arthropods in the animal kingdom: A search for as reliable outgroup for internal arthropod phylogeny. Molecajar Phylogenetics and Evolution 9, 481-488.
	28	Hagedorn, T.R. (1998). Determining the structure and number of phylogenetic invariants, manuscript, College of New Jersey.
	29	Hagedorn, T.R. and Landweber, L.F. (1998). Phylogenetic invariants and geometry, manuscript, College of New Jersey and Princeton University.
	30	Sridhar Hannenhalli , Pavel Pevzner, Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.178-189, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225112]
	31	Hasegawa, M., Kishino, H. and Yano, T. (1985). Dating of the human-ape splitting by a molecular clock of mitochondrial DNA.Journal of Molecular Evolution 22, 160-174.
	32	Hendy, M.D. and Penny, D. (1996). Complete families of linear invariants for some stochastic models of sequence evolution, with and without the molecular clock assumption. Journal of Computational Biology 3, 19-31.
	33	Jin, L. and Nei, M. (1990). Limitations of the evolutionary parsimony method of phylogenetic analysis. Molecular Biology and Evolution 7, 82-102.
	34	jukes,T.H, and Cantor C.R. (1969). Evolution of prorein molecules. In Mammalian Protein Metabolism (Ed: H.N. Munro) Academic Press, New York. pp. 21-132.
	35	Haim Kaplan , Ron Shamir , Robert E. Tarjan, Faster and simpler algorithm for sorting signed permutations by reversals, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.344-351, January 05-07, 1997, New Orleans, Louisiana, United States
	36	Kimura, M. (1980). A simple method for estimating evolutionary rate of base substitutions through comparative studies of nucleotide sequences. Journal of Molecular Evolution 16, 111-120.
	37	Kimura, M. (1981). Estimation of evolutionary sequences between homologous nucleotide sequences. Proceedings of the National Academy of Sciences (U.S.A.) 78, 454-458.
	38	Lake, J.A. (1987). A rate-independent technique for analysis of nucleic acid sequences: Evolutionary parsimony. Molecular Biology and Evolution 4, 167-191.
	39	Maddsion, V. and Mad&son, W. (1995). Tree of Life metazoa page, http://phylogeny, arizona.edu/tree/eukaryotes/animals/animals.html
	40	Nguyen, T and Speed, T.P. (1992). A derivation of all linear invariants for a nonbalanced transversion model. Journal of Molecular Evolution 35, 60-76.
	41	Pe'er, I. and Shamir, R. (1998). The median problems for breakpoints are NP-complete. manuscript, University of Washington.
	42	Rouse, G.W. and Fauchald, K. (1995). The articulation of annelids. 2oologica Scripta 24, 269-301
	43	Ruppert, E.E. and Barnes, B.D. (1994). Invertebrate Zoology. Saunders, Philadelphia.
	44	Sankoff, D. (1990). Designer invariants for large phylogenies. Molecular Biology and Evolution 7, 255-269.
	45	David Sankoff , Mathieu Blanchette, The Median Problem for Breakpoints in Comparative Genomics, Proceedings of the Third Annual International Conference on Computing and Combinatorics, p.251-264, August 20-22, 1997
	46	Sankoff, D. and Blanchette, M. (1998a). Multiple genome rearrangement and breakpoint phylogeny. Journal of Computational Biology 5, 555-570.
	47	Sankoff, D., and Blanchette, M. 1998b. Phylogenetic invariants for metazoan mitochondrial genome evolution. In: Genome Informatics 1998 (Eds: S. Miyano and T. Takagi) Universal Academy Press, Tokyo, pp. 22-23.
	48	Sankoff, D., and Blanchette, M. (1999) Comparative genomics via phylogenetic invariants for Jukes-Cantor semigroups. In:Proceedings of the International Conference on Stochastic Models (Eds: L. Gorostiza and G.Ivanoff) Conference Proceedings Series, Canadian Mathematical Society, in press.
	49	Sankoff, D., Leduc, G., Antoine, N., Paquin, B., Lang, B.F., and Cedergren, R.J. (1992). Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome. Proceedings of the National Academy of Sciences USA 89, 6575-6579.
	50	David Sankoff , Marie-Noelle Parent , Isabelle Marchand , Vincent Ferretti, On the Nadeau-Taylor Theory of Conserved Chromosome Segments, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.262-274, June 30-July 02, 1997
	51	Steel, M.A. (1994). Recovering a tree from the leaf colorations it generates under a Markov model. Applied Mathematics Letters 7, 19-23.
	52	Steel, M. A. and Fu, Y.X. (1995). Classifying and counting linear phylogenetic invariants for the Jukes-Cantor model. Journal of Computational Biology 2, 39-47.
	53	Steel, M. A., Szekeley, L.A., Erdos, P.L., Waddell, P. (1993) A complete family of phylogenetic invariants for any number of taxa under Kimura's 3ST model. New Zealand Journal of Botany 31, 289-296
	54	L. A. Székely , M. A. Steel , P. L. Erdős, Fourier calculus on evolutionary trees, Advances in Applied Mathematics, v.14 n.2, p.200-216, June 1993 [doi>10.1006/aama.1993.1011]
	55	Tajima, F. and Nei, M. (1984). Estimation of evolutionary distance between nucleotide sequences. Molecular Biology and Evolution 1, 269-285.
	56	Tamura, K. (1992). Estimation of the number of nucleotide substitutions when there are strong transitiontransversion and G + C-content biases. Molecular Biology and Evolution 9, 678-687.
	57	Tamura, K. and Nei, M. (1993). Estimation of the number of nucleotide substitutions in the control region of mitochondrial DNA in humans and chimtmnzees. Molecular Biology and Evolution 10, 512-526.
	58	Valentine, J.W. (nd) University of California Museum of Paleontology Metazoa Systematics Page, http://www, ucmp.berkeley, edu/phyla/met azoasy, ht ml
	59	Wada, H., and N. Satoh. 1994. Details of the evolutionary history from invertebrates to vertebrates, as deduced from the sequences of 18S rDNA. P~ings of the National Academy of Sciences (U.S.A.) 91, 1801- 1804.
	60	Watterson,G.A., Ewens, W.J., Hall, T.E. and Morgan, A. (1982). The chromosome inversion problem. Journal of Theoretical Biology 99, 1-7.

CITED BY 3

	Li-San Wang , Tandy Warnow, Estimating true evolutionary distances between genomes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.637-646, July 2001, Hersonissos, Greece
	Bernard M. E. Moret , Jijun Tang , Li-San Wang , Tandy Warnow, Steps toward accurate reconstructions of phylogenies from gene-order data, Journal of Computer and System Sciences, v.65 n.3, p.508-525, November 2002
	Niklas Eriksen, Expected number of breakpoints after t random reversals in genomes with duplicate genes, Discrete Applied Mathematics, v.156 n.12, p.2320-2335, June, 2008