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

Construction of random perfect phylogeny matrix

Authors Mehdi Sadeghi, Hamid Pezeshk, Changiz Eslahchi, et al

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]

 

Other article by this author:

The interpretation of protein structures based on graph theory and contact map

Mahnaz Habibi, Changiz Eslahchi, Mehdi Sadeghi, et al

Open Access Bioinformatics 2010, 2:127-137

Published Date: 21 September 2010

Readers of this article also read:

Emerging and future therapies for hemophilia

Carr ME, Tortella BJ

Journal of Blood Medicine 2015, 6:245-255

Published Date: 3 September 2015

Methacrylic-based nanogels for the pH-sensitive delivery of 5-Fluorouracil in the colon

Ashwanikumar N, Kumar NA, Nair SA, Kumar GS

International Journal of Nanomedicine 2012, 7:5769-5779

Published Date: 15 November 2012

A novel preparation method for silicone oil nanoemulsions and its application for coating hair with silicone

Hu Z, Liao M, Chen Y, Cai Y, Meng L, Liu Y, Lv N, Liu Z, Yuan W

International Journal of Nanomedicine 2012, 7:5719-5724

Published Date: 12 November 2012

Cross-linked acrylic hydrogel for the controlled delivery of hydrophobic drugs in cancer therapy

Deepa G, Thulasidasan AK, Anto RJ, Pillai JJ, Kumar GS

International Journal of Nanomedicine 2012, 7:4077-4088

Published Date: 27 July 2012

Crystallization after intravitreal ganciclovir injection

Pitipol Choopong, Nattaporn Tesavibul, Nattawut Rodanant

Clinical Ophthalmology 2010, 4:709-711

Published Date: 14 July 2010