个体单位型组装问题MEC模型的算法研究与比较

摘要

分析和识别单体型对复杂疾病致病基因的精确定位有重要作用，但是在当前的实验技术下直接测定个体单体型所需的时间和金钱上的花费过于昂贵，因此利用计算机技术来确定个体的单体型有其重要的现实意义。单体型组装问题是利用个体DNA 测序片段数据推出该个体一对单体型的计算问题。单体型组装问题的大部分计算模型都被证明是NP 难的，缺乏实用的算法。
　　 在单体型组装问题的众多模型中，MEC(Minimum Error Correction)模型是最符合实际且信息丢失最少的模型。基于MEC 模型，本文在详细研究了MCMC算法如何使用一条由单体型组成的马尔科夫链来解决该组装问题的基础上，借鉴其建立位点结构图的新颖思想，结合遗传算法，提出GAMEC 算法，并针对问题设计适应度函数和启发式算子对由单体型构成的种群进行选择、交叉和变异。研制了计算机程序，使用模拟数据和19 号染色体上的真实数据对两种算法分别进行实验。实验结果表明，两种算法均能够准确进行单体型估计，并且组装出具有较高精确度和重构率的单体型，GAMEC 算法计算速度优于MCMC 算法，而MCMC算法具有更好的适应性。这两种算法描述的是单体型组装的一般框架，均能够被应用于各种测序技术产生的序列数据。