skip to content
Dovepress - Open Access to Scientific and Medical Research
View our mobile site

8847

Construction of random perfect phylogeny matrix

Original Research

(2017) Views  (350) Full article downloads

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.

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

 






 

Other articles by Dr Changiz Eslahchi



Readers of this article also read:

Discrimination between biological interfaces and crystal-packing contacts
An online conserved SSR discovery through cross-species comparison
Computer applications for prediction of protein–protein interactions and rational drug design
Use of electronic medical records in oncology outcomes research
Novel mechanisms of central nervous system damage in HIV infection
Pharmacogenomics of drug efficacy in the interferon treatment of chronic hepatitis C using classification algorithms
The interpretation of protein structures based on graph theory and contact map
Affinity of estrogens for human progesterone receptor A and B monomers and risk of breast cancer: a comparative molecular modeling study
Homozygous N396T mutation in Gaucher disease: Portuguese sisters with markedly different phenotypes
Changes in corneal parameters at confocal microscopy in treated glaucoma patients
  • Testimonials

    "... I was impressed at the rapidity of publication from submission to final acceptance." Dr Edwin Thrower, PhD, Yale University