title: Construction of random perfect phylogeny matrix.
abstract: OBJECTIVE
  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.
  
  
  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(n(2), nm)) algorithm for the random construction of such a phylogeny matrix. The running time of any algorithm for solving this problem would be Ω (nm).
  
  
  CONCLUSIONS
  We have developed software, RAPPER, based on this algorithm, which is available at http://bioinf.cs.ipm.ir/softwares/RAPPER.
authors.affiliation: National Institute of Genetic Engineering and Biotechnology, Tehran, Iran.
authors.forename: Mehdi
authors.initials: M
authors.lastname: Sadeghi
authors.forename: Hamid
authors.initials: H
authors.lastname: Pezeshk
authors.forename: Changiz
authors.initials: C
authors.lastname: Eslahchi
authors.forename: Sara
authors.initials: S
authors.lastname: Ahmadian
authors.forename: Sepideh Mah
authors.initials: SM
authors.lastname: Abadi