Title: Matrix Completion and Performance Guarantees for Single Individual Haplotyping,
Abstract: Single individual haplotyping is an NP-hard problem that emerges when
attempting to reconstruct an organism's inherited genetic variations using data
typically generated by high-throughput DNA sequencing platforms. Genomes of
diploid organisms, including humans, are organized into homologous pairs of
chromosomes that differ from each other in a relatively small number of variant
positions. Haplotypes are ordered sequences of the nucleotides in the variant
positions of the chromosomes in a homologous pair; for diploids, haplotypes
associated with a pair of chromosomes may be conveniently represented by means
of complementary binary sequences. In this paper, we consider a binary matrix
factorization formulation of the single individual haplotyping problem and
efficiently solve it by means of alternating minimization. We analyze the
convergence properties of the alternating minimization algorithm and establish
theoretical bounds for the achievable haplotype reconstruction error. The
proposed technique is shown to outperform existing methods when applied to
synthetic as well as real-world Fosmid-based HapMap NA12878 datasets.