Back to Journals » Advances and Applications in Bioinformatics and Chemistry » Volume 3

Construction of random perfect phylogeny matrix

Authors Sadeghi M, Pezeshk H, Eslahchi C, Ahmadian S, Abadi SM

Published 16 November 2010 Volume 2010:3 Pages 89—96

DOI https://doi.org/10.2147/AABC.S13397

Review by Single-blind

Peer reviewer comments 3

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
 

Creative Commons License 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]