单体型装配问题及其算法

作者：王瑞省; 吴凌云; 张继红; 章祥荪分支定界动态聚类单体型装配snpmec问题

摘要：单核苷酸多态性（SNP）单体型装配问题就是从给定的来自某人染色体的SNP片段中去除错误，重构出醛可能与原来片段一致的单体型．这个问题有几个不同的模型：最少片段去除（MFR）问题，最少SNP去除（MSR）问题以及最少错误纠正（MEC）问题．前两个问题的复杂性与算法已有一些学者研究过．第三个问题已被证明是NP完全问题，但这个问题的实际算法还没有，该文对MEC问题给出了一个分支定界算法，这个算法能得到问题的全局最优解．通过这个算法对实际数据的计算说明了MEC模型的合理性，即在一定条件下，通过修正最少的错误重构出的单体型确实是真实的单体型．由于分支定界算法对这样一个NP完全问题不能在叮接受的时间内解规模较大的问题，文中又给出了求解MEC问题的两个基于动态聚类的算法，以便对规模较大的问题在可接受的时间内得到近似最优解．数值实际表明这两个算法很快，很有效．这两个算法总能得到与分支定界找到的全局最优解很接近的近似最优解．鉴于MEC问题是NP完全的，这两个算法是有效的、实际的算法．

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社