Parameterized Algorithm of the Individual Haplotyping MSR Problem with Mate-Pairs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
The individual haplotyping MSR (minimum SNP removal) problem is the computational problem of inducing an individual's haplotypes from one's DNA fragments sequencing data by dropping minimum SNPs (single-nucleotide polymorphisms). To solve the problem, Bafna, et al. had provided an algorithm of time complexity O(2kn2m) with the number of fragments m, the SNP sites n, the maximum number of holes k in a fragment. In the case that there are some Mate-Pairs, since the number of holes in a Mate-Pair can reach 100, Bafna's algorithm is impracticable. Based on the characters of DNA fragments, this paper presents a new algorithm of time complexity O((n-1)(k1-1)k222h+ (k1+1)2h+nk2+mk1) with the maximum number of SNP sites that a fragment covers k1(no more than n), the maximum number of the fragments covering a SNP site k2(usually no more than 19) and the maximum number of fragments covering a SNP site whose value is unknown at the SNP site h (no more than k2). Since the time complexity is not directly related with k, the algorithm can deal with the MSR problem with Mate-Pairs efficiently, and is more scalable and applicable in practice.
