Construction of random perfect phylogeny matrix
Mehdi Sadeghi1,2, Hamid Pezeshk4, Changiz Eslahchi3,5, Sara Ahmadian6, Sepideh Mah Abadi6
1National Institute of Genetic Engineering and Biotechnology, Tehran, Iran; 2School of Computer Science, 3School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran; 4School of Mathematics, Statistics and Computer Sciences, Center of Excellence in Biomathematics, College of Science, University of Tehran, Tehran, Iran; 5Department of Mathematics, Shahid Beheshti University, G.C., Tehran, Iran; 6Department 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(n2, 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
This work is published and licensed by Dove Medical Press Limited. The full terms of this license are available at https://www.dovepress.com/terms.php and incorporate the Creative Commons Attribution - Non Commercial (unported, v3.0) License. By accessing the work you hereby accept the Terms. Non-commercial uses of the work are permitted without any further permission from Dove Medical Press Limited, provided the work is properly attributed. For permission for commercial use of this work, please see paragraphs 4.2 and 5 of our Terms.Download Article [PDF] View Full Text [HTML][Machine readable]