Sparse Tensor Decomposition for Haplotype Assembly of Diploids and Polyploids.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Haplotype assembly is crucial for understanding genetic variation effects on phenotypes.
• NP-hard nature of haplotype assembly is exacerbated by advanced sequencing technologies and polyploidy.
• Scalable and accurate methods are needed for diploid and polyploid haplotype assembly.

Purpose of the Study:

• To develop a novel framework for haplotype assembly using sparse tensor decomposition.
• To introduce an algorithm, AltHap, for reconstructing haplotypes in diploid and polyploid organisms.
• To provide theoretical guarantees on the performance and error correction of the proposed method.

Main Methods:

• Formulating haplotype assembly as a sparse tensor decomposition problem.
• Developing the AltHap algorithm for iterative decomposition and haplotype reconstruction.
• Theoretical analysis of AltHap's performance, convergence, and error correction capabilities.

Main Results:

• AltHap effectively reconstructs haplotypes for both diploid and polyploid species.
• The framework is applicable to various ploidy levels and allelic complexities.
• Theoretical guarantees on minimum error correction scores and correct phasing rates were established.

Conclusions:

• AltHap offers a robust and scalable solution for haplotype assembly.
• The method shows competitive performance for diploids and significantly outperforms existing methods for polyploids.
• The freely available AltHap code facilitates broader application in genomic studies.