%0 Journal Article
%T Construction of random perfect phylogeny matrix
%A Mehdi Sadeghi
%A Hamid Pezeshk
%A Changiz Eslahchi
%A et al
%J Advances and Applications in Bioinformatics and Chemistry
%D 2010
%I Dove Medical Press
%R http://dx.doi.org/10.2147/AABC.S13397
%X nstruction of random perfect phylogeny matrix Original Research (3639) Total Article Views Authors: Mehdi Sadeghi, Hamid Pezeshk, Changiz Eslahchi, et al Published Date November 2010 Volume 2010:3 Pages 89 - 96 DOI: http://dx.doi.org/10.2147/AABC.S13397 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.
%K perfect phylogeny
%K minimum allele frequency (MAF)
%K tree
%K recursive algorithm
%U https://www.dovepress.com/construction-of-random-perfect-phylogeny-matrix-peer-reviewed-article-AABC