Abstract
Single nucleotide polymorphisms (SNPs) is one of the most considered topics. This phenomenon of genetic polymorphism is the most frequent human genetic variation and corresponding to numerous applications such as medical diagnosis, drug design and phylogenis. It is also helpful for tracking disease genes. The complete sequence of SNP varieties from a single copy of chromosomes is called a haplotype. To determine haplotypes for a single individual, one alternative method proposed in [1, 2] is based on the DNA fragments and the methodology of Shotgun Sequencing Assembly. Every DNA fragment contains several SNPs information. After an appropriate assembly of the fragments, we can get the haplotypes for a single individuals. But it is difficult to get error-free fragments in the begining, how to remove errors to obtain valid assembly of all corrected fragments becomes the first problem. Since different error types are considered, two version of the problem, Minimal Fragments Removal(MFR) and Minimal SNPs Removal(MSR), were introduced in [1]. In this paper, we revised the original algorithm for MSR on fragments at most k holes. Although the original one was claimed to run in O(mn2k+2) [3], with more careful analysis, we found that it should be an O(mn2 + n2k+2) algorithm. Moreover, the existing algorithms for MFR only use the fragments from diploid genomes as input data. We extended the algorithm such that it also works robustly on the gapless fragments from polyploid genomes.