Academic Journals Database
Disseminating quality controlled scientific knowledge

Construction of random perfect phylogeny matrix

Author(s): Mehdi Sadeghi | Hamid Pezeshk | Changiz Eslahchi | et al

Journal: Advances and Applications in Bioinformatics and Chemistry
ISSN 1178-6949

Volume: 2010;
Issue: default;
Start page: 89;
Date: 2010;
Original page

Mehdi Sadeghi1,2, Hamid Pezeshk4, Changiz Eslahchi3,5, Sara Ahmadian6, Sepideh Mah Abadi61National 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, IranPurpose: 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 perfect phylogeny, minimum allele frequency (MAF), tree, recursive algorithm 

Tango Rapperswil
Tango Rapperswil

RPA Switzerland

Robotic Process Automation Switzerland