Construction of random perfect phylogeny matrix

Mehdi Sadeghi^1,2, Hamid Pezeshk⁴, Changiz Eslahchi^3,5, Sara Ahmadian⁶, Sepideh Mah Abadi^6
1National Institute of Genetic Engineering and Biotechnology, Tehran, Iran; ²School of Computer Science, ³School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran; ⁴School of Mathematics, Statistics and Computer Sciences, Center of Excellence in Biomathematics, College of Science, University of Tehran, Tehran, Iran; ⁵Department of Mathematics, Shahid Beheshti University, G.C., Tehran, Iran; ⁶Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

Purpose: Interest in developing methods appropriate for mapping increasing amounts of genome-wide molecular data are increasing rapidly. There is also an increasing need for methods that are able to efficiently simulate such data.
Patients and methods: In this article, we provide a graph-theory approach to find the necessary and sufficient conditions for the existence of a phylogeny matrix with k nonidentical haplotypes, n single nucleotide polymorphisms (SNPs), and a population size of m for which the minimum allele frequency of each SNP is between two specific numbers a and b.
Results: We introduce an O(max(n², nm)) algorithm for the random construction of such a phylogeny matrix. The running time of any algorithm for solving this problem would be Ω (nm).
Conclusion: We have developed software, RAPPER, based on this algorithm, which is available at http://bioinf.cs.ipm.ir/softwares/RAPPER.

Keywords: perfect phylogeny, minimum allele frequency (MAF), tree, recursive algorithm