Spectral-Stitching Algorithm for Haplotype Phasing

This repository implements the Spectral-Stitching algorithm for haplotype phasing proposed in:

• Yuxin Chen, Govinda Kamath, Changho Suh, and David Tse, “Community recovery in graphs with locality,” International Conference on Machine Learning, pp. 689-698, June 2016.
  • Paper (ICML)
  • Paper (Arxiv)
  • Slides (Computational Genomics Summer Institute)
  • Slides (International Conference on Machine Learning)
  • Github Repo

The design of the Spectral-Stitching algorithm leverages connections between haplotype phasing and the problem of community detection, where communities have to be inferred based on the friendship graph of users. The algorithm is shown to be efficient especially when the coverage is relatively deep (at least > 5X).

The main program is implemented in Python. An evaluation program (implemented in MATLAB and R) is also provided for evaluating the phasing accuracy on NA12878 WGS data (see 10X paper).

If you have any questions, feel free to contact

Banghua Zhu, Tsinghua University
Yuxin Chen, Princeton University
David Tse, Stanford University