title: Estimating population size via line graph reconstruction.
abstract: BACKGROUND
  We propose a novel graph theoretic method to estimate haplotype population size from genotype data. The method considers only the potential sharing of haplotypes between individuals and is based on transforming the graph of potential haplotype sharing into a line graph using a minimum number of edge and vertex deletions.
  
  
  RESULTS
  We show that the resulting line graph deletion problems are NP complete and provide exact integer programming solutions for them. We test our approach using extensive simulations of multiple population evolution and genotypes sampling scenarios. Our results also indicate that the method may be useful in comparing populations and it may be used as a first step in a method for haplotype phasing.
  
  
  CONCLUSIONS
  Our computational experiments show that when most of the sharings are true sharings the problem can be solved very fast and the estimated size is very close to the true size; when many of the potential sharings do not stem from true haplotype sharing, our method gives reasonable lower bounds on the underlying number of haplotypes. In comparison, a naive approach of phasing the input genotypes provides trivial upper bounds of twice the number of genotypes.
authors.affiliation: School of Science and Engineering, Reykjavík University, Menntavegur 1, Reykjavik 101, Iceland. bjarnivh@ru.is.
authors.forename: Bjarni V
authors.initials: BV
authors.lastname: Halldórsson
authors.forename: Dima
authors.initials: D
authors.lastname: Blokh
authors.forename: Roded
authors.initials: R
authors.lastname: Sharan