Haplotype Assembly Using Rank Minimization

For many years, DNA sequencing was done using Sanger’s method introduced in 1975. Nowdays, Next Generation Sequencing (NGS) becomes popular due to its speed and resolution [1]. In diploids, there are two homologous copies of each somatic chromosome. Homologous pairs mean that each chromosome consists of similar nucleotides sequences except a little difference. The frequent variation of a single nucleotide is named as the Single Nucleotide Polymorphism (SNP). The sequence of SNPs of each chromosome is called haplotype. The haplotype of an individual is used in drug-design and genome wide association studies [2]. Unfortunately, NGS does not provide haplotype information. Haplotype can be found using high-cost experiments or computational methods [3]. Using the NGS data for Haplotyping is known as haplotype assembly which is a NP-Hard problem. A new method for haplotype assembly is SDhaP [4] which is superior to ReFHap [2] and HapCut [5]. The core idea of SDhaP is correlation clustering. In this paper, a novel modeling for the haplotype data and NGS reads is presented based on [6]. This model results in a constraint on the rank of the read matrix. Then, the problem of haplotype assembly converted to a rank minimization optimization. Since the rank functional which is from vector space of matrices to the positive integer set, is non-convex, it can be relaxed to the nuclear norm, i.e. the sum of matrix singular values. This relaxation has been well mentioned as the power of convex relaxation [7-8]. Simulations on the data addressed in [9] shows that the proposed approach improves the resolution of haplotype assembly in terms of reconstruction rate compared to the new method, SDhaP [4].

Keywords:

Haplotype Assembly , Next Generation Sequencing (NGS) , Rank minimization