Fourier Transform Inequalities for Phylogenetic Trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fourier Transform Inequalities for Phylogenetic Trees

Full text

Pdf (198 KB)

Source

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) archive
Volume 6 , Issue 1 (January 2009) table of contents

Pages 89-95

Year of Publication: 2009

ISSN:1545-5963

Author

Frederick A. Matsen

UC Berkeley, Berkeley

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 58, Citation Count: 0

Additional Information:

abstract references index terms

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

DOI Bookmark:	10.1109/TCBB.2008.68

ABSTRACT

Phylogenetic invariants are not the only constraints on site-pattern frequency vectors for phylogenetic trees. A mutation matrix, by its definition, is the exponential of a matrix with non-negative off-diagonal entries; this positivity requirement implies non-trivial constraints on the site-pattern frequency vectors. We call these additional constraints "edge-parameter inequalities." In this paper, we first motivate the edge-parameter inequalities by considering a pathological site-pattern frequency vector corresponding to a quartet tree with a negative internal edge. This site-pattern frequency vector nevertheless satisfies all of the constraints described up to now in the literature. We next describe two complete sets of edge-parameter inequalities for the group-based models; these constraints are square-free monomial inequalities in the Fourier transformed coordinates. These inequalities, along with the phylogenetic invariants, form a complete description of the set of site-pattern frequency vectors corresponding to \emph{bona fide} trees. Said in mathematical language, this paper explicitly presents two finite lists of inequalities in Fourier coordinates of the form "monomial $\leq 1$," each list characterizing the phylogenetically relevant semialgebraic subsets of the phylogenetic varieties.

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	E.S. Allman and J.A. Rhodes, "Phylogenetic Invariants for the General Markov Model of Sequence Mutation," Math. Biosciences, vol. 186, no. 2, pp. 113-144, 2003.
	2	M. Casanellas and J. Fernandez-Sanchez, "Geometry of the Kimura 3- Parameter Model," Advances in Applied Math., vol. 41, no. 3, pp. 265-292, 2008.
	3	J.A. Cavender and J. Felsenstein, "Invariants of Phylogenies in a Simple Case with Discrete States," J. Classification, vol. 4, pp. 57-71, 1987.
	4	J. Kim, "Slicing Hyperdimensional Oranges: The Geometry of Phylogenetic Estimation," Molecular Phylogenetics and Evolution, vol. 17, no. 1, pp. 58-75, Oct. 2000.
	5	B. Sturmfels and S. Sullivant, "Toric Ideals of Phylogenetic Invariants," J. Computational Biology, vol. 12, no. 2, pp. 204-228, Mar. 2005.
	6	E.S. Allman and J.A. Rhodes, "Phylogenetic Ideals and Varieties for the General Markov Model," Advances in Applied Math., vol. 40, no. 2, pp. 127- 148, 2008.
	7	J. Felsenstein, Inferring Phylogenies. Sinauer Press, 2004.
	8	E. Allman and J. Rhodes, "Phylogenetic Invariants," Reconstructing Evolution: New Mathematical and Computational Advances, O. Gascuel and M. Steel, eds., Oxford Univ. Press, 2007.
	9	Serkan Hosten , Amit Khetan , Bernd Sturmfels, Solving the Likelihood Equations, Foundations of Computational Mathematics, v.5 n.4, p.389-407, November 2005 [doi>10.1007/s10208-004-0156-8]
	10	N. Eriksson, "Using Invariants for Phylogenetic Tree Construction," to be published in Emerging Applications of Algebraic Geometry, M. Putinar and S. Sullivant, eds., Springer, arXiv:0709.2890, 2008.
	11	M. Kimura, "A Simple Method for Estimating Evolutionary Rates of Base Substitutions through Comparative Studies of Nucleotide Sequences," J. Molecular Evolution, vol. 16, no. 2, pp. 111-120, Dec. 1980.
	12	D.W. Stroock, An Introduction to Markov Processes. Springer-Verlag, 2005.
	13	C. Semple and M. Steel, Phylogenetics. Oxford Univ. Press, 2003.
	14	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]
	15	D. Bryant, "Extending Tree Models to Split Networks," Algebraic Statistics for Computational Biology, L. Pachter and B. Sturmfels, eds., Cambridge Univ. Press, 2005.
	16	V. Moulton and M. Steel, "Peeling Phylogenetic "Oranges"," Advances in Applied Math., vol. 33, no. 4, pp. 710-727, 2004.
	17	M.D. Hendy and D. Penny, "A Framework for the Quantitative Study of Evolutionary Trees," Systematic Zoology, vol. 38, no. 4, pp. 297-309, 1989.
	18	M.D. Hendy, "The Relationship between Simple Evolutionary Tree Models and Observable Sequence Data," Systematic Zoology, vol. 38, no. 4, pp. 301- 321, 1989.
	19	S.N. Evans and T.P. Speed, "Invariants of Some Probability Models Used in Phylogenetic Inference," Annals of Statistics, vol. 21, no. 1, pp. 355-377, 1993.
	20	F.A. Matsen and M. Steel, "Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology," Systematic Biology, vol. 56, no. 5, pp. 767-775, Oct. 2007.