————————————
基金项目:国家自然科学基金资助项目(61165009);广西自然科学基金资助项目(2011GXNSFB018068, 2012GXNSFAA053219);“八桂
学者”工程专项基金资助项目;广西高等学校科学技术研究基金资助项目(2013YB028)
作者简介:吴璟莉(1978-),女,副教授、博士、CCF 会员,主研方向:生物信息学;梁彬彬,硕士研究生;李志欣,副教授、博士;
王 华,硕士研究生
收稿日期:2012-08-13 修回日期:2012-10-16 E-mail:wjlhappy@mailbox.gxnu.edu.cn
一种快速精确的个体单体型重建算法
吴璟莉 ,梁彬彬 ,李志欣 ,王 华
(广西师范大学计算机科学与信息工程学院,广西 桂林 541004)
摘 要:在最少错误更正模型的基础上,提出一种重建单体型的启发式算法 H-MEC。按照单体型的单核苷酸多态性(SNP)位点顺
序依次构建算法步骤,根据某 SNP 位点取值将覆盖该 SNP 位点的片段划分为 2 个集合,利用包含片段数较多集合中的片段进行重
建。使用 HapMap 计划发布的 CEPH 样本中的 60 个个体,在 1 号染色体的单体型上进行实验。结果表明,H-MEC 算法在各种参
数设置下,能获得较 Fast Hare 算法和 DGS 算法更高的单体型重建率。此外,该算法在重建长单体型时也具有较高的执行效率。
关键词:单核苷酸多态性;单体型;最少错误更正;启发式;重建
A Fast and Accurate Reconstruction Algorithm for
Individual Haplotype
WU Jing -li, LIANG Bin -bin, LI Zhi -xin, WANG Hua
(College of Computer Science and Information Technology, Guangxi Normal University, Guilin 541004, China)
【Abstract】A heuristic algorithm for haplotype reconstrucion, named H-MEC, is proposed based on the Minimum Error Correction(MEC)
model. H-MEC reconstructs the columns of a pair of haplotypes one by one. It partitions the Single Nucleotide Polymorphisms(SNP)
fragments that cover some SNP site into two sets according to the values of the corresponding SNP site, and reconstructs haplotypes by
using the fragments of the set which contains more fragments. The experiments are conducted by using the haplotypes on the chromosomes
1 of 60 individuals in the CEPH sample, which are released by the international HapMap project. Experimental results indicate that under
various parameter settings, H-MEC can obtain higher reconstruction rate than Fast Hare algorithm and DGS algorithm. Moreover, H-MEC
still has high efficiency even for reconstructing long haplotypes.
【Key words】Single Nucleotide Polymorphisms(SNP); haplotype; Minimum Error Correction(MEC); heuristic; reconstruction
DOI: 10.3969/j.issn.1000-3428.2013.09.050
1
概述
目前 单体型问题得到了越来越广泛的关注与研究 。 在
人口结构分析 、 人类群体扩张以及其他相关研究中 , 单体
型有着重要的应用 , 而且单体型数据在复杂疾病的关联分
析以及致病基因的定位中起着非常重要的作用
[1]
。虽然可以
通过生物实验技术测定生物个体的单体型 , 但在当前的实
验技术条件下 , 若直接通过单纯的生物学实验手段测定
一个个体的单体型 , 无论从时间或是成本上来说都太过昂
贵 , 因此 , 利用计算机技术确定个体的单体型 , 即单体型
检测 , 既经济又具有极其重要的现实意义 。 该问题主要分
为 三 大类 :
(1)
基于群体基因型数据的群体 单体型检测
[2]
;
(2)
基于测序片段数据的群体单体型检测
[3]
;
(3)
基于测序片
段数据的个体单体型检测
[4]
。本文对第
(3)
类问题进行研究 。
近年来 , 在二倍体个体单体型重建问题上已取得一定
的研究成果 , 主要针对以下
4
个计算模型展开 : 最少片段
删除
(Minimum Fragment R emoval , MFR)
[4]
, 最少
SNP
删除
(Minimum SNP Rem oval , MSR)
[4]
,最长单体型重建
(Longest
Haplotype Reconstruction , LHR)
[4]
和最少错误更正
(Mini mum
Error Cor rection , MEC)
[5]
。 文献
[6-7]
提出了求解
MFR
和
MSR
模型的动态规划算法 ; 文献
[8]
提出求解
LHR
模型的
动态规划算法 ;文献
[9]
设计了求解
MEC
模型的分值定界算
法 ; 文献
[10]
利用动态规划方法提出求解
MEC
模型的精确
算法 。然而在一般情况下 ,这
4
个模型是
NP
难的 ,上述精
确算法并不能高效求解这些模型的一般情形 。 因此 , 研究
人员提出了许多求解该问题的启发式算法并获得 了 较好的