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

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