单体型组装MEC问题的参数化算法研究

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

Research on parameterized algorithm of Haplotypes assembly MEC problem

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.