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

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (35): 57-60.

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

谢民主^1,2,王建新²,陈建二²

1.湖南师范大学物理与信息科学学院，长沙 410081
2.中南大学信息科学与工程学院，长沙 410083

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-12-11 发布日期:2007-12-11
通讯作者: 谢民主

Research on parameterized algorithm of Haplotypes assembly MEC problem

XIE Min-zhu^1,2,WANG Jian-xin²,CHEN Jian-er²

1.College of Physics and Information Science，Hunan Normal University，Changsha 410081，China
2.School of Information Science and Engineering，Central South University，Changsha 410083，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-12-11 Published:2007-12-11
Contact: XIE Min-zhu

摘要/Abstract

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

关键词: 生物信息学, 单体型检测, 参数化算法, 单核苷酸多态性

Abstract: 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.

Key words: bioinformatics, haplotyping, parameterized algorithm, SNPs（Single-Nucleotide Polymorphisms）

谢民主^1,2,王建新²,陈建二². 单体型组装MEC问题的参数化算法研究[J]. 计算机工程与应用, 2007, 43(35): 57-60.

XIE Min-zhu^1,2,WANG Jian-xin²,CHEN Jian-er². Research on parameterized algorithm of Haplotypes assembly MEC problem[J]. Computer Engineering and Applications, 2007, 43(35): 57-60.

[1]	孙志伟，单渊博，蔡润身，王林. 快速的致病基因分析方法[J]. 计算机工程与应用, 2017, 53(17): 47-52.
[2]	张琪，刘立芳，马磊，贺建峰. 一种基于HBV序列的SNP位点检测方法研究[J]. 计算机工程与应用, 2014, 50(23): 145-150.
[3]	姚雄武，郑金华，李晶，文诗华. 遗传算法和单体型组装加权最小字符翻转问题[J]. 计算机工程与应用, 2010, 46(8): 217-220.
[4]	李松倍，谢江，张武，武频. 蛋白质相互作用网络的相似子网搜索问题研究[J]. 计算机工程与应用, 2010, 46(3): 33-35.
[5]	谢民主¹，刘新求^2，3. 枚举单体型组装问题多个最优解的遗传算法设计[J]. 计算机工程与应用, 2010, 46(11): 7-9.
[6]	马宝山¹，朱义胜¹，陈玉珍². 用多种统计特征识别基因序列[J]. 计算机工程与应用, 2009, 45(29): 118-119.
[7]	李敏,陈建二,王建新. 基于复杂网络理论的PPI网络拓扑分析[J]. 计算机工程与应用, 2008, 44(8): 20-22.
[8]	吴德敏^1,2,陈俊³. 双序列比对的算法研究[J]. 计算机工程与应用, 2008, 44(36): 48-50.
[9]	胡桂武. 基于免疫GA与Gibbs的模体识别算法[J]. 计算机工程与应用, 2007, 43(18): 72-74.
[10]	胡桂武. 竞争PSO在多序列联配中的应用 [J]. 计算机工程与应用, 2006, 42(9期): 23-.