书书书
收稿日期:20131129;修回日期:20140121
作者简介:蒋安纳(1979),女,江苏苏州人,讲师,硕士,主要研究方向为生物信息学、并行计算(anna_nfu@163.com);徐逸卿(1981),男,江
苏南京人,讲师,博士研究生,主要研究方向为计算机网络;董程玲(1986),女,江苏苏州人,硕士,主要研究方向为生物信息学;童春发(1963),
男,安徽巢湖人,教授,博导,主要研究方向为林木遗传连锁图谱构建和
QTL定位、生物信息学、常规林木遗传模型分析等.
分子标记多位点排序的并行计算
蒋安纳
a
,徐逸卿
a
,董程玲
a
,童春发
b
(南京林业大学 a.信息科学技术学院;b.森林资源与环境学院,南京 210037)
摘 要:为了对一组连锁的分子标记位点获得正确的排序进而构建生物遗传连锁图谱,提出了并行算法 PM
MASLH,针对 F2作图群体,通过基于消息传递接口并行最大最小蚂蚁系统求解连锁的多个分子标记位点排序,
使用隐马尔可夫模型计算一列有序标记位点所获得的极大似然值作为排序的目标函数。计算机模拟结果表明,
该算法执行效率高、计算稳定,排序的功效优于著名的连锁作图软件 Mapmaker。
关键词:分子标记排序;并行计算;最大最小蚂蚁系统;隐马尔可夫模型;F2群体
中图分类号:TP181;TP301.6 文献标志码:A 文章编号:10013695(2015)01007505
doi:10.3969/j.issn.10013695.2015.01.018
Parallelcomputationfororderinglinkagegroupofmolecularmarkers
JIANGAnna
a
,XUYiqing
a
,DONGChengling
a
,TONGChunfa
b
(a.CollegeofInformationScience&Technology,b.CollegeofForestResources&Environment,NanjingForestryUniversity,Nanjing210037,
China)
Abstract:Inordertosortthelinkagegroupofmolecularmarkersforconstructingthegeneticlinkagemap,thispaperpresen
tedaparallelalgorithmnamedPMMASLH.Itwasbasedonmaxminantsystem
,proposedfororderingalargenumberoflinked
molecularmarkersinanF2population.Itchosetheobjectfunctionoforderingasthelikelihoodofanorderdmarkerswithhid
denMarkovmodelmethod.Thesimulationexperimentsshowthatthealgorithmisofhighefficiencyandstability,anditspower
ismuchhigherthanthatofthefamouslinkagemappingsoftware,Mapmaker.
Keywords:molecularmarkerordering;parallelcomputation;maxminantsystem;hiddenMarkovmodels;F2population
遗传连锁图谱(geneticlinkagemap)是通过遗传距离来反
映遗传标记在基因组上的相对位置,是基因组研究中一个重要
组成部 分
[1]
。遗 传 连 锁 图 谱 在 动 植 物 分 子 标 记 辅 助 选 择
(markerassistedselection,MAS)育 种、数 量 性 状 基 因 位 点
(
quantitativetraitlocus,QTL)定位以及基因组序列组装研究中
有着极其重要的意义
[2,3]
。
遗传连锁图谱构建涉及到分子标记数据的获取和统计分
析等步骤
[4,5]
。首先,需要建立适当的杂交作图群体,如在农
作物中通常由纯系产生杂交二代(F2)或回交(BC)群体作为
作图群体。在作图群体中一般随机抽取几百个个体,并获取每
个个体的分子标记(如
SSR、AFLP等)基因型数据。其次,通
过两点连锁分析获得任意两个标记位点间的重组率和 LOD
值,在其基础上将众多的分子标记划分成若干个连锁群。最
后,对每个连锁群中分子标记按照一定的算法进行排序,并确
定相邻标记位点间的遗传距离,至此便完成了连锁图谱的构
建。其中,分子标记的排序是关键步骤,它关系到遗传连锁图
谱的准确性,关系到后续研究诸如
QTL定位的可靠性。然而
标记排序属于 TSP,当连锁群中标记数比较多时(>20),不可
能用穷尽法获得全局最优解,只能使用近似算法求解。随着二
代高通量测序技术的发展,利用简化基因组测序(RADseq)在
群体中很容易获得上万个分子标记
[6,7]
,因此有必要研究快速
高效的针对上百个分子标记位点的排序算法。
目前最著名的使用最广泛的遗传连锁图谱作图软件是
Mapmaker
[8]
,但它已于 1993年 1月停止更新。Mapmaker基于
DOS操作系统,在 Windows2000版本平台上也能运行良好,但
已无法在更高级的
Windows平台上稳定运行。由于生物科研
人员缺乏编程背景,而计算机编程人员又缺乏相关的生物背景
知识,因此遗传连锁图谱作图软件的开发多年停滞不前,生物
科研人员仍被迫使用
Mapmaker。
Mapmaker没有公开标记排序算法,其排序的效率也没有评
价过,其他软 件 也 大 致 如 此。本 文 采 用 基 于 消 息 传 递 接 口
(messagepassinginterface,MPI)的并行最大最小蚂蚁系统 PM
MASLH
求解 F2代群体的分子遗传标记排序问题。使用隐马尔
可夫模型进行多位点连锁分析,并将有序标记位点的极大似然
函数值作为标记排序的目标函数。通过大量的计算机随机模拟
来评价该算法的精准度,并与
Mapmaker的计算结果作比较。
!
最大最小蚂蚁系统模型
自然界中蚂蚁寻找食物时会向环境分泌信息素(phero
mone)以吸引其他蚂蚁过来,信息素会随时间推移逐渐挥发至
消失,信息素的浓度大小表示了路径的远近。其他觅食的蚂蚁
被高浓度信息素吸引过来,经过一段时间,某条路径上走过的蚂
蚁越多,则信息素越强,后来的蚂蚁选择该条路径的概率也就越
大。久而久之,蚂蚁能够找到食物到洞穴的一条最短路径。
第 32卷第 1期
2015年 1月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.32No.1
Jan.2015