论文部分内容阅读
单核苷酸多态性（SNP）单体型装配问题就是从给定的来自某人染色体的SNP片段中去除错误，重构出醛可能与原来片段一致的单体型．这个问题有几个不同的模型：最少片段去除（MFR）问题，最少SNP去除（MSR）问题以及最少错误纠正（MEC）问题．前两个问题的复杂性与算法已有一些学者研究过．第三个问题已被证明是NP完全问题，但这个问题的实际算法还没有，该文对MEC问题给出了一个分支定界算法，这个算法能得到问题的全局最优解．通过这个算法对实际数据的计算说明了MEC模型的合理性，即在一定条件下，通过修正最少的错误重构出