Abstract: The haplotype assembly MEC problem is the computational problem of inducing a pair of haplotypes from an individual’s DNA fragments sequencing data by correcting minimum SNPs.Based on the characters of DNA fragments，the paper introduces a parameterized algorithm of time complexity O（nk₂2^k₂+mlogm+mk₁） with m fragments，n SNPs，the maximum number of SNP sites that a fragment covers k₁（usually smaller than 10） and the maximum number of the fragments covering a SNP site k₂（usually no more than 10）.For the practical fragment data，the algorithm can solve the MEC problem efficiently even if m and n are larger and it is scalable and applicable in practice.

Key words: bioinformatics, haplotyping, parameterized algorithm, SNPs（Single-Nucleotide Polymorphisms）

摘要： 单体型组装MEC问题指如何利用个体的DNA测序片断数据，翻转最少的SNP位点值以确定该个体单体型的计算问题。根据片段数据的特点提出了一个时间复杂度为 O（nk₂2^k₂+mlogm+mk₁）的参数化算法，其中m为片段数，n为单体型的SNP位点数，k1为一个片断覆盖的最大SNP位点数（通常小于10），k₂为覆盖同一SNP位点的片段的最大数（通常不大于10）。对于实际DNA测序中的片段数据，即使m和n都相当大，该算法也可以在较短的时间得到MEC问题的精确解，具有良好的可扩展性和较高的实用价值。

关键词: 生物信息学, 单体型检测, 参数化算法, 单核苷酸多态性