ＣＮ４３—１２５８／ＴＰ
计算机工程与科学
２００５年第２７卷第２期
ＩＳＳＮ１００７—１３０Ｘ
ＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩ￡ＮＣＥ
Ｖ０１．２７，Ｎｏ．２，２００５
文章编号：１００７－１３０Ｘ（２００５）０２－００７１－０３
ＤＮＡ序列拼接的分布式并行处理。
ＡＤｉｓｔｒｉｂｕｔｅｄＰａｒａｌｌｅｌＡｌｇｏｒｉｔｈｍｆｏｒＤＮＡ
Ｓｅｅｌ｝ｕｅｎｃｅＵｅｎｃｅｌｂｍｅｓｓＡ
ｓｅ
厂
方小永。骆志刚
ＦＡＮＧＸｉａｏ－ｙｏｎｇ。ＬＵＯＺｈｉ－ｇａｎｇ
（并行与分布处理国家重点实验室，湖南长沙４１００７３）
（Ｎａｔｉｏｎａｌ
Ｌａｂｏｒａｔｏｒｙ
ｆｏｒＰａｒａｌｌｅｌａｎｄＤｉｓｔＨｂｕｔｅｄＰｒｏｃｅｓｓｉｎｇ－Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ）
摘要：针对分布式存储环境，本文提出一种ＤＮＡ序列拼接的并行算法，分别对序列拼接中ＯＶＥＲＬＡＰ、ＬＡＹＯＵＴ
和ＣＯＮＳＥＮＳＵＳ阶段的串行处理过程和并行算法进行了描述，并给出了算法复杂性分析。数值试验结果表明，算法是高
效的。
Ａｂｓｔｒａｃｔ：ＡｎｏｖｅｌｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｆｏｒＤＮＡｓｅｑｕｅｎｃｅａｓｓｅｍｂｌｙｕｎｄｅｒｔｈｅｄｉｓｔｒｉｂｕｔｅｄｍｅｍｏｒｙ
ｅｎｖｉｒｏｎｍｅｎｔｉｓｐｒｅｓｅｎｔｅｄ
ｉｎｔｈｉｓｐａｐｅｒ．Ｔｈｅｓｅｒｉａｌｐｒｏｃｅｓｓｉｎｇｐｒｏｃｅｄｕｒｅａｎｄｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍ
ｆｏｒＯＶＥＲＬＡＰ，ＬＡＹｏＵＴａｎｄＣＯＮＳＥＮＳＵＳｏｆｔｈｅ
ＤＮＡｓｅｑｕｅｎｃｅａｓｓｅｍｂｌｙａｒｅｄｅｓｃｒｉｂｅｄ
ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｔｈｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅ
ａｌｇｏｒｉｔｈｍ
ｉｓａｎａｌｙｚｅｄ．Ｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔ
ｔｈｉｓ
ａｌｇｏｒｉｔｈｍｉｓ
ｏｆ‘
ｈｉｇｈｅｆｆｉｃｉｅｎｃｙ．
关键词：生物信息；序列拼接；并行处理；分布式
Ｋｅｙｗｏｒｄｓ：ｂｉｏｉｎｆｏｒｍａｔｉｃｓ；ｓｅｑｕｅｎｃｅａｓｓｅｍｂＩｙ；ｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍ；ｄｉｓｔｒｉｂｕｔｅｄｍｅｍｏｒｙ
中图分类号：Ｑ８１１．４文献标识码：Ａ
１
引言
和Ⅱ几ＥＲ［引。此外，还有其它一些各有特点的拼接算法，如ＴＩＧＲ｛３］、ＣＡＰ４［４］等。ＤＮＡ序列拼接在存储和时间开基因组计划的目标是获得所研究的生物的全基因组序
销上都非常巨大。例如，ＰＨＲＡＰ在对规模为１０００００条列，而序列拼接是基因组测序阶段生物信息学研究的最基ｒｅａｄ的螺旋藻序列进行拼接时，所需要的内存空间将达到本、最重要的问题。众所周知，生物的基因组是指该生物所６Ｇ，在曙光３０００上耗时８６５１７．２５９２秒，约合２４小时［５］。有遗传物质的总和，绝大部分基因组由ＤＮＡ（脱氧核糖核因而，ＤＮＡ序列拼接并行处理的研究有着理论和现实的重酸）组成。ＤＮＡ是由核苷酸单体构成的线性、无分支的多要意义。这方面国外较著名的是ＳＰＳＯＦＴ（ｈｔｔｐ：／／ｗｗｗ．聚分子。核苷酸由碱基区分，ＤＮＡ中，碱基分别是腺嘌呤ｓｐｓｏｆｔｃｏｒｎ），国内中科院计算所智能信息处理实验室在曙（Ａｄｅｎｉｎｅ）、胞嘧啶（Ｃｙｔｏｓｉｎｅ）、鸟嘌呤（Ｇｕａｎｉｎｅ）和胸腺嘧光３０００上实现了ＰＨＲＡＰ的并行化［５］。
啶（Ｔｈｙｍｉｎｅ），分别用字母Ａ、Ｃ、Ｇ、Ｔ表示。基因组测序就本文提出分布式存储环境下进行ＤＮＡ序列拼接的一是要确定ＤＮＡ分子的碱基序列。由于基因组的每条染色种新的并行算法，这是基于Ｈａｍｉｌｔｏｎ图的一类拼接方法。体长度可达数百万碱基对以上，而按目前的测序技术，一次我们将首先给出算法的推导过程和描述，然后对算法复杂实验最多只能直接测得不大于７５０个碱基，因此一个长的性进行分析并给出算法的性能评估。
ＤＮＡ分子序列只能通过将一系列短序列拼接起来而得到。将基因组测序得到的上千万个小片段序列通过比对再正确２算法
拼接起来，就是ＤＮＡ序列拼接和组装所要解决的问题。
目前，ＤＮＡ序列拼接算法可以分为两类，它们分别基２．１
ＤＮＡ序列拼接问题的描述
于Ｈａｍｉｌｔｏｎ图和Ｅｕｌｅｒ图，最具代表的分别是ＰＨＲＡＰ［１］
目前，主要的基因测序方法有鸟枪法、克隆重叠群法和
・
收稿日期：２００３－０８－２５；修订日期：２００３－１０－３０
作者简介：方小永（１９７８一），男，河南汝南人，硕士生，研究方向为生物信息处理；骆志刚，博士，教授，研究方向为生物信息学和高性能并行计算。
通讯地址：４１００７３湖南省长沙市砚瓦池正街４７号并行与分布处理国家重点实验室；Ｔｅｌ：（０７３１）４５７３６６６；Ｅ－ｍａｉｌ：ｘｙｆａｎｇｎｕｄｔ＠
１６３．ｅｏｍ
Ａｄｄｒｅｓｓ：ＮａｔｉｏｎａｌＬａｂｏｒａｔｏｒｙｆｏｒＰａｒａｌｌｅｌａｎｄＤｉｓｔｒｉｂｕｔｅｄＰｒｏｃｅｓｓｉｎｇ，４７ＹａｎｗａｃｈｉＳｔ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ
４１００７３，Ｐ．ＲＣｈｉｎａ
万
方数据７】
定向鸟枪法［６］。无论何种方法，都需要将ＤＮＡ分子（或其长片段）先经过克隆形成若干个拷贝，将这些拷贝打碎成若干条短的、可以直接测序的片段（称为Ｒｅａｄ）。这些Ｒｅａｄ之间存在着大小不等的重叠（Ｏｖｅｒｌａｐ）区域。ＤＮＡ序列拼接就是要通过这些Ｒｅａｄ重新构造出原始的ＤＮＡ序列。
２．２算法的推导和描述
基于Ｈａｍｉｌｔｏｎ图方法的基本思想是［７］：首先将所有的Ｒｅａｄ构成一个有向图Ｇ，每个Ｒｅａｄ看成一个结点，如果两个ｒｅａｄ之间存在有重叠，那么在相应的结点之间就存在有一条边；然后，通过寻找经过每个Ｒｅａｄ一次且仅一次的一条路径，就将序列拼接问题转化成Ｈａｍｉｌｔｏｎ路经问题。这种方法可以分为如下三步：（１）找出序列片段间的重叠信息；（２）将存在有重叠的片段组合起来，形成一个Ｃｏｎｔｉｇ结构；（３）根据片段中每个碱基的质量值，在Ｃｏｎｔｉｇ结构中寻找一条最终序列，称作“Ｃｏｎｓｅｎｓｕｓ”序列。
基于Ｈａｍｉｌｔｏｎ图方法的拼接算法分以下三个阶段：
（１）ＯＶＥＩ也ＡＰ，对所有的片段进行两两比对，以获得可能存在的重叠部分的信息；
（２）ＬＡＹＯＵＴ，根据得到的重叠信息将存在重叠的片
段建立一种组合关系，形成一个链接体，称作“Ｃｏｎｔｉｇ”；
（３）ＣＯＮＳＥＮＳＵＳ，根据构成链接体Ｃｏｎｔｉｇ的片段的
原始质量数据，在链接体中寻找一条质量最重的序列路径，
并获得与路径相对应的序列，称作“Ｃｏｎｓｅｎｓｕｓ”序列。
本文算法的描述过程是，首先给出上述每一阶段的串行处理过程，然后给出本步的并行算法描述。算法描述中
处理机设为ｍ＋１个，记为Ｐ０，Ｐ１，．一，Ｒ。
２．２．１
ＯＶＥＲＬＡＰ
两个片段可以拼接的必要条件是这两个片段之间存在一个重叠部分ｏｖｅｒｌａｐ，并且在重叠部分有一个最小长度为ｍｉｎ＿ｚｏｏｒｄ的精确匹配区域ｍａｔｃｈ。如果ｍａｔｃｈ的长度超过ｎ“２ｘ＿ｗｏｒｄ，则认为这两个片段是几乎相同的而不适合拼接。因此，算法首先需要找出所有满足条件的片段对（称
为ＲｅａｄＰａｉｒ）［１］。另外，如果两个片段可以进行拼接，那么
只有那些首、尾相接的ＲｅａｄＰａｉｒ才有意义，否则由于口ｖｅｒｌａｐ长度太长，可以认为两个片段是同一条序列。因此可以设置一个参数ｍａｘ—ｏｖｅｒｌａｐ，首先把每个片段划分为首、尾两部分（对于那些长度较短的片段，首、尾可以重叠），然后只需拿一个片段的首或尾与另一个片段的尾或首进行比对即可。
找出所有满足上述条件的ＲｅａｄＰａｉｒ后，通过序列比对算法Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ来精确计算每个ＲｅａｄＰａｉｒ可能存在
的Ｏｖｅｒｌａｐ，并对每一个可能的ｏｖｅｒｌａｐ计算Ｓｍｉｔｈ－Ｗａｔｅｒ—
ｍａｎ得分Ｓｃｏｒｅ，如果Ｓｃｏｒｅ大于ｒａｉｎ—ｓｃｏｒｅ则认为Ｏｖｅｒ—ｌａｐ，否则不予接受。另外，为了提高拼接的准确度，需要对每个Ｏｖｅｒｌａｐ采用ＬＬＲ（ＴｈｅＬａｒｇｅｓｔＬｉｋｅｌｉｈｏｏｄＲａｔｉｏ，简称ＬＬＲ）进行打分［１］，如果该Ｏｖｅｒｌａｐ的ＬＬＲ大于０，则认
为是真Ｏｖｅｒｌａｐ，否则不予接受。
这一部分的串行处理过程描述如下：
输入：片段集合卜｛ｆｏ，＾，…，＾一１｝。
输出：Ｏｖｅｒｌａｐ集合Ｏ一｛Ｏ（五，乃）Ｊ五，力∈ｒ，且＾和乃存在Ｏｖｅｒｌａｐ｝；包含Ｏｖｅｒｌａｐ的Ｃｏｎｔｉｇ集合ｔ＇２一｛Ｃ１，Ｃ２，…，Ｇ｝。
参数：ｍｉｎ＿＿ｗａｒｄ：可接受的ｍａｔｃｈ的最小长度；ｍ∞一ｗｏｒｄ：可接
７２
万
方数据受的ｍａｔｃｈ的最大长度；ｒａｉｎ＿ｓｃｏｒｅ：可接受的Ｏｖｅｒｌａｐ的最小Ｓｍｉｔｈ－
Ｗａｔｅｒｍａｎ得分；ｍａｘ＿ｏｖｅｒｌａｐ：可接受的Ｏｖｅｒｌａｐ的最大长度。
Ｓｔｅｐｌ：若１１中尚未进行比对的片段不少于两个，则从＿ｒ中任意取两个片段：，ｉ，五。
Ｓｔｅｐ２：依据ｍａｘ＿ｏｖｅｒｌａｐ参数，分别把五和兀分为首、尾两部分；比较五的首和乃的尾，比较五的尾和＾的首；找出五和力
中所有满足条件“长度在ｒａｉｎ—ｚｏｏｒｄ和一一ｗｏｒｄ范围内”的ｍａｔｃｈ；若在五和＾中存在满足条件的ｍａｔｃｈ，则转Ｓｔｅｐ３，否则转
Ｓｔｅｐｌ。
Ｓｔｅｐ３：对Ｓｔｅｐ２得到的每一个ｍａｔｃｈ，首先要覆盖整个重叠区域（可能不是精确匹配）；然后对整个重叠区域实施Ｓｍｉｔｈ—Ｗａｔｅｒ－
ｍａｎ算法，以精确寻找，ｆ和＾之间存在的Ｏｖｅｒｌａｐ，并计算该ｐ
ｖｅｒｌａｐ的Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ得分；取Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ得分最高的
那个ｍａｔｃｈ覆盖的重叠区域作为Ｏｖｅｒｌａｐ，并把其Ｓｍｉｔｈ—Ｗａｔｅｒ—
ｍａｒｌ得分记为Ｓｃｏｒｅ（五，乃）。
’
Ｓｔｅｐ４：若Ｓｃｏｒｅ（五，五）小于ｍｉｎ—ｓｃｏｒｅ，则转Ｓｔｅｐｌ，否则转
Ｓｔｅｐ５。
Ｓｔｅｐ５：对Ｏｖｅｒｌａｐ利用Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法进行回溯，并计算每条回溯路径下的Ｌ上瓜，以寻找五和＾的最佳对齐方式（ａｌｉｇｎ—
ｍｅｎｔ）。
Ｓｔｅｐ６：取ＬＬＲ最高的那个ａｌｉｇｎｍｅｎｔ作为Ｏｖｅｒｌａｐ（，ｆ，ｆＪ），然后把Ｏｖｅｒｌａｐ（，ｆ，ｆＪ）输出到相应的Ｃｏｎｔｉｇ，并保存相应的重叠信息，然后转Ｓｔｅｐｌ执行；该操作中Ｃｏｎｔｉｇ是动态创建的，并且依据
输出的Ｏｖｅｒｌａｐ动态合并。
在本阶段，我们需要对佗条片段两两比对以寻找０一ｖｅｒｌａｐ，即每个片段需要和其它片段比对以寻找Ｏｖｅｒｌａｐ。因此，我们只要对全体片段数据进行正确分割，每个片段就可以独立执行比对操作，可以并行处理。我们的做法是：把本阶段全体片段数据比对操作总量分为ｍ＋１组，分别分派给ｍ＋１个处理机执行。为保持负载平衡，我们在任务分派时对全体片断数据进行动态分割。
并行算法描述如下：
输入、输出及参数设置同本阶段的串行处理过程；
设布尔变量ｃｏｎｔｒｏｌ控制算法对数据进行动态分割，初始为
ｔｒｕｅ；
Ｓｔｅｐｌ：Ｐ０作如下操作：
（１）Ｆｏｒ（ｉ＝０；ｉ＜ｎ－－１；）
｛
Ｆｏｒ（ｊ＝ｉ＋１；ｊ＜ｎ；ｊ＋＋）
｛对五，五执行本阶段串行处理过程Ｓｔｅｐ２～
Ｓｔｅｐ６｝；
ｉｆ（ｃｏｎｔｒ０１）
｛ｃｏｎｔｒｏｌ＝ｆａｌｓｅ；
ｉ—ｉ＋２（ｍ＋１）一１；｝
ｅｌｓｅ
｛ｃｏｎｔｒｏｌ＝ｔｒｕｅ；ｉ＝ｉ＋１；）
｝
（２）Ｆｏｒ（ｉ＝１；ｉ＜ｍ＋１；ｉ＋＋）
｛接收Ｐｉ（１≤ｉ≤ｍ）的处理结果数据包并解包；｝
（３）处理Ｐｏ，Ｐ１，…，Ｐ０１的执行结果以形成Ｃｏｎｔｉｇ集合
ｎ，终止程序执行；
Ｓｔｅｐ２：Ｂ（１≤女≤ｍ）作以下操作：
（１）Ｆｏｒ（ｉ＝ｋ；ｉ＜ｎ一１；）
｛
Ｆｏｒ（ｊ—ｉ＋１；ｊ＜ｎ；ｊ＋＋）
｛对五，五执行本阶段串行处理过程Ｓｔｅｐ２～
Ｓｔｅｐ６｝；
ｉｆ（ｃｏｎｔｒ０１）
｛ｃｏｎｔｒｏｌ＝ｆａｌｓｅ；
ｉ—ｉ＋２（ｍ＋１）一（２ｋ＋１）；｝
ｅｌｓｅ
｛ｃｏｎｔｒｏｌ＝ｔｒｕｅ；ｉ＝ｉ＋（２ｋ＋１）；｝｝
（２）对执行结果进行打包并发送给Ｐ０；
２．２．２
ＬＡＹＯＵＴ
若片段工和＾存在重叠区域，则称厂ｆ和＾直接相关；若片段五与片段＾直接相关，片段正与片段＾直接
相关，片段＾与片段＾不直接相关，则称片段五与片段＾间接相关。
输出Ｃｏｎｓｅｎｓｕｓ序列。为保证精度，每个片段在投票前需
对其质量值进行修正，修正的依据是该片段保存的重叠区域信息。由于片段间的投票操作是彼此独立的，因此可以并行处理。
这一部分的串行处理过程描述如下：
输入：计算所有片段偏移量以后的Ｃｏｎｔｉｇ集合１２＝｛ｃ１，Ｑ，…，Ｑ｝；与每个Ｃｏｎｔｉｇ对应的片段集合ｎ，ｎ，…，ｎ。
输出：与每个Ｃｏｎｔｉｇ对应的ｃｏｎｓｅｎｓｕｓ序列Ｓ１，Ｓｚ，…，＆。操作：处理ｎ中的每个Ｃｏｎｔｉｇ。对每个Ｃｏｎｔｉｇ，设它包含的所有片段按照其偏移量从小到大依次排列为：，０，＾，…，＾，记为，一｛，０，＾，…，＾）。则对每个Ｃｏｎｔｉｇ，作以下操作：
Ｓｔｅｐｌ：若，不空，则从首位置取下一个片段五。
Ｓｔｅｐ２：依据ＯＶＥＲＬＡＰ阶段保存的重叠信息对，ｆ的碱基字符排列和质量值进行修正，使得五的质量值最大。
在ＯＶＥＲＬＡＰ阶段，我们在输出Ｏｖｅｒｌａｐ时，要求Ｏｖｅｒ－
ｌａｐ输出到相应的Ｃｏｎｔｉｇ，即把所有具有直接相关或间接相关关系的片段汇集在同一Ｃｏｎｔｉｇ里，这些里的片段最终将形成一个ｃｏｎｓｅｎｓｕｓ序列Ｓ。为此，需要计算每一条片段相对于Ｓ起始位置的偏移量。我们需要分别对每个Ｃｏｎｔｉｇ包含的片段计算其偏移量以决定片段间的组合关系。
这一部分的串行处理过程描述如下：
输入：包含Ｏｖｅｒｌａｐ的Ｃｏｎｔｉｇ集合１２＝｛Ｃａ，ｃ２，…，Ｇ）；
输出：计算所有片段偏移量以后的Ｃｏｎｔｉｇ集合ｎ＝｛ｃ１，Ｃ２，
…，Ｑ｝；
操作：处理ｎ中的每个Ｃｏｎｔｉｇ；对每个Ｃｏｎｔｉｇ，作以下操作：
Ｓｔｅｐｌ：对该Ｃｏｎｔｉｇ包含的Ｏｖｅｒｌａｐ按照ＬＬＲ以降序排列，并删除那些ＬＬＲ小于０的Ｏｖｅｒｌａｐ（因为这样的Ｏｖｅｒｌａｐ不适合拼接）。
Ｓｔｅｐ２：取下ＬＬＲ最高的那个Ｏｖｅｒｌａｐ（＾，ｆＪ）。若五的起始位
置在，ｉ的左端，则取五的起始位置为参考原点，否则取力的起始位置为参考原点。
Ｓｔｅｐ３：处理该Ｃｏｎｔｉｇ包含的每个Ｏｖｅｒｌａｐ（五，五），即计算五，乃
相对于参考原点的偏移量（若片段的起始位置在参考原点左端，则偏移量为负，否则为正）；包含参考原点的那个片段的偏移量为０。
Ｓｔｅｐ４：取偏移量最小的那个片段的起始位置为参考原点，并把该片段的偏移量取为Ｏ；依据新的参考原点，修正所有片段的偏移量。
在本阶段，由于各个Ｃｏｎｔｉｇ彼此独立，我们采用工作池的动态任务分派方法将其并行化。
’
并行算法描述如下：
输入、输出及参数设置同本阶段串行处理过程。
设参数ｃｏｕｎｔ表示已经处理完毕的Ｃｏｎｔｉｇ数目，初始为０。Ｓｔｅｐｌ：Ｐｏ作如下操作：
（１）从ｎ中取出ｒｎ个Ｃｏｎｔｉｇ：Ｃｘ，Ｃｚ，…，．Ｃｋ，分别发送给Ｐ１，
Ｐ２，…，Ｐｍ；ｃｏｕｎｔ一０；０＝／２－－｛Ｃｌ，Ｑ’．．・，Ｇ｝。
（２）如果ｎ不空，则从ｎ中取出一个Ｃｏｎｔｉｇ：Ｇ（１≤ｉ≤＾）；对ｃｆ执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ４，ｌ＂２＝０－－｛Ｇ｝，∞勰￡增
１。
（３）接收Ｐｉ（１≤ｆ≤ｍ）的处理结果，ｃｏｕｒⅡ增１。
如果ｎ不空，则从０中取出一个Ｃｏｎｔｉｇ：Ｃ／（１≤ｉ≤屉）发送给Ｂ，ｎ＝ｎ一｛ｃｉ），否则通知Ｐｆ终止执行。
（４）如果ｃｏｕｒｔ等于五，则终止执行，否则转（２）执行。Ｓｔｅｐ２：Ｐｆ（１≤ｉ≤ｍ）作以下操作：（１）接收来自Ｐ０的Ｃｏｎｔｉｇ数据ｃｆ；
（２）对ｃ｝执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ４；（３）发送处理结果给Ｐｏ，转（１）执行。
需要指出的是，若Ｃｏｎｔｉｇ个数忌小于处理机个数ｍ＋１，会出现某些处理机空闲的情况。但是，由于相对总计算量而言，本阶段的计算量非常小，对整体并行效率影响不大。
２．２．３
ＣＯＮＳＥＮＳＵＳ
ＤＮＡ序列拼接程序的输入文件有两个，一个是序列文件（ＳｅｑｕｅｎｃｅＦｉｌｅ），另一个是与序列文件对应的质量文件
（ＱｕａｎｌｉｔｙＦｉｌｅ）。序列文件包含将要进行拼接的片段数据
（Ｒｅａｄ），质量文件包括与序列文件中每个片段中每个碱基对应的质量值数据（ＱｕａｌｉｔｙＶａｌｕｅ）。所谓一个碱基的质量值口是指该碱基的可信度大小，它与该碱基测序错误概率Ｐ的关系［１３为：
ｑ一一１０ｌｏｇ（ｐ）
由此可知，Ｐ越小，ｑ就越大，该碱基的可信度就越大。一个片段的质量值是指该片段上所有碱基质量值之和，ＣＯＮＳＥＮＳＵＳ阶段的最终目的就是寻找一条质量值最大的Ｃｏｎｓｅｎｓｕｓ序列。
我们采取每个片段分别对Ｃｏｎｓｅｎｓｕｓ序列投票的方法
万
方数据Ｓｔｅｐ３：执行＾的投票操作：首先依据五的偏移量定位＾在ｃｏｎｓｅｎｓｕｓ序列Ｓ上的起始位置ＢｅｇｉｎＰｏｓｉｔｉｏｎ和结束位置ＥｎｄＰｏｓｉｔｉｏｎ；对于Ｓ上从ＢｅｇｉｎＰｏｓｉｔｉｏｎ到ＥｎｄＰｏｓｉｔｉｏｎ的每一个位置，把，ｆ在该位置上的某种类型的碱基（Ａ、Ｃ、Ｇ、Ｔ之一）质量值都有ａ…ｃ
累加在Ｓ在该位置上的那种类型的碱基质量值上（Ｓ上每个位置
ｇｔ四种类型碱基的质量值累加器，初始值为Ｏ）。Ｓｔｅｐ４：从，删除＾，转Ｓｔｅｐｌ执行，直到，为空。
Ｓｔｅｐ５：对于Ｓ上每个位置输出累加质量值之和最大的那种类型碱基字符，最终输出一条质量值之和最大的一条序列，即ｃｏｉｌ—ｓｅｎ５ｕｓ序列。
对于本阶段算法，Ｃｏｎｔｉｇ之间彼此独立，每一个Ｃｏｎｔｉｇ
内部片段之间的投票操作彼此独立。因此，我们可以顺序
处理每个Ｃｏｎｔｉｇ，对每个Ｃｏｎｔｉｇ可以采用静态任务分配方
法将其并行化。
并行算法描述如下：
输入、输出及参数设置同本阶段串行处理过程。
设参数ｃｏｕｎｔ表示已经处理完毕的Ｃｏｎｔｉｇ数目，其初始为０。Ｓｔｅｐｌ：Ｐｏ作如下操作：
（１）０若不空，则从０中取出一个Ｃｏｎｔｉｇ：Ｇ（１≤ｉ≤志），否则通知Ｐ１，Ｐ２，…，ｆ，卅终止执行。
（２）把ｃ：ｆ包含的片段按偏移量从小到大的顺序依次划分为ｍ
＋１组：ｒ０，ｎ，ｎ，…，Ｌ；把ｎ，ｒ２，…，ｎ分别发送给Ｐ１，Ｐ２，…，
Ｐｍ；１２＝０－－｛ｃｆ｝。
（３）把ｒ０取作，，执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ５。（４）接收Ｐ１，Ｐ２，…，Ｐｋ的执行结果，合并所有处理机的执行结果，ｃｏｕｎｔ增１。
（５）如果ｃｏｕｎｔ等于ｋ，则终止执行，否则转（１）执行。Ｓｔｅｐ２：Ｐｉ（１≤筵；ｍ）作以下操作：
（１）接收来自Ｐｏ的Ｃｏｎｔｉｇ数据中的片段数据ｒｉ（１≤ｉ≤ｍ）。（２）把ｎ取作ｒ’，执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ５；（３）发送处理结果给Ｐ０，转（１）执行。
３性能分析
设算法要处理咒个片段，产生Ｌ个Ｏｖｅｒｌａｐ，ｋ个Ｃｏｎ－ｔｉｇ，每通信一次所用启动时间为Ｌ。，每发送一个数据所
用时间为Ｔ出。。３．１
ｏＶ腿ＩＡＰ
设每两个片段执行本阶段串行处理过程所用时间平均
为Ｔｒ吲，则：
数为咒（行一１）／２，执行时间为以（咒一１）ｋ／２。
本阶段串行处理过程的计算复杂性为Ｏ（ｎ２），比对次并行算法执行时间等于通信时闳Ｔ—。媳上诗簋赋迥、
了ｋ。。每个处理机分得片段个数为竹／（优＋１），因此Ｔ。巾为（ｎ／（ｍ＋１））（ｎ／（ｍ十１）一１）Ｔｏ／２，Ｌ。。为ＬＴ出。＋
ｍＬ。，并行算法执行时间为Ｌ一十ｋｐ＝（挖／（ｍ＋１））
（ｎ／（ｍ＋１）一１）Ｔ，吲／２＋ＬＴ出。十ｍＴ＃ａ。。
（下转第７７页）
７３
Ｐｒｏｇｒａｍ分别传递ＰｌｏＰ６参数，然后调用程序ＣｏｍｍＰｒｏ—表１测试环境
ｇｒａｍ即可实现ＰｌｏＰ６的功能。封装设计在信息抽象基础上进行描述、提取、加工，最后返回具体的需求结果。这对于大型的信息系统来说，增加业务功能却不增加代码，省去了大量的重复性工作，这一点是有非常好的应用前景的。
参考文献：
［１］李木金，李桔，王光兴．一种基于Ｗｅｂ的网络智能管理模型及
表２测试结果
其实现［Ｊ］．软件学报，１９９９，１０（１１）：１１９１－１１９３．
［２］段海新，杨家海，吴建平．基于Ｗｅｂ和数据库的网络管理系统
的设计与实现［Ｊ］．软件学报，２０００，１１（４）：４６８－４７２．
１（
行）７６８９．０９
１．０００１００［３］侯小梅，毛宗源，张波．基于遗传算法的管理信息系统的智能
串４
１９８９．４０３．８６５９６．６３分解口］．系统工程与电子技术，２０００，２２（１）：５－７．
６１４９５．２１５．１４２８５．７１［４ｑ张文增，孙振国，赵冬斌，等．基于Ｂ／Ｓ结构的实验室管理信
８
１１４８．１７
６．６９７
８３．７１
息系统开发方案ｆＪ］．计算机工程与应用，２００２，３８（１１）：２３２－
２３３．
Ｅ５］路军，王亚东，王晓龙．面向对象的管理信息Ａｇｅｎｔ系统［Ｊ］．
计算机工程与应用，２０００，３６（３）：３０－３２．
１（
行）１３７３１．４０１．０００１００串４
３７６０．２９３．６５２９１＿２９（上接第７３页）
６２４６０．４３５．５８１９３．０１加速比为（，ｚ（竹一１）‰／２）／（（ｎ／（ｍ＋１））（ｎ／（ｍ＋１）一１）
８
２０６９．５４
６．６３５
８２．９４
Ｌ“／２＋ＬＬ‰＋ｍＬ，）ｏ
数值试验结果表明，该算法具有良好的加速比。
３．２
ＬＡＹｏＵＴ
设处理一个Ｏｖｅｒｌａｐ所用时间平均为Ｌ础ｐ，则：
５结束语
本阶段串行处理过程的计算复杂度为０（Ｌ），执行时
目前的拼接算法中，如ＰＨＲＡＰ，某些步骤计算局部性间为Ｌ１ｋ砌。。
不明显，直接并行难度较大。我们在认真分析已有拼接算并行算法执行时间等于最后一个结束计算的处理机法的基础上，结合我们针对的并行处理环境，提出一种新的只（１≤ｉ≤ｍ）与Ｐｏ的通信时间Ｌ一加上最后一个结束计
算的处理机Ｐ，（ｏ≤Ｊ≤ｍ）的计算时间了ｋ，Ｔａ聊为
拼接算法。算法的性能分析和数值试验表明算法是高
效的。
ＬＬ州。／（ｍ＋１），瓦～为２忌Ｔ刍／（ｍ＋１）＋（Ｌ＋竹）Ｔ出。／
（ｍ＋１），因此并行算法执行时间为瓦一＋Ｔａ哪一２ｋＬ。／
（ｍ＋１）＋（Ｌ＋咒）Ｔｋ／（ｍ＋１）＋Ｌ‰。／（ｍ＋１）。参考文献：
Ｉ－１－１
ＰＧｒｅｅｍＤｏｃｕｍｅｎｔａｔｉｏｎｆｏｒＰｈｒａｐ［ＥＢ／ＯＬ－］．ｈｔｔｐ：／／ｂｏｚｅｍ－
＋１）＋Ｌｋ。／（ｍ＋１））。
加速比为Ｌ１ｋ砌，／（２ｋｌｋ。／（ｍ＋１）＋（Ｌ＋ｎ）ｔ‰／（ｍ
ａｍ
ｍｂｔ．ｗａｓｈｉｎｇｔｏｎ．ｅｄｕ／ｐｈｒａｐ．ｄｏｃｓ／ｐｈｒａｐ．ｈｔｍｌ，２００３－０７．
［２］Ｐ
ＡＰｅｖｚｎｅｒ，Ｈａｉｘｕ
Ｔａｎｇ，ＭＳＷａｔｅｒｍａｎ．ＡＮｅｗＡｐｐｒｏａｃｈ
３．３
ＣｏＮＳＥＮＳＵＳ
ｔＯ
ＦｒａｇｍｅｎｔＡｓｓｅｍｂｌｙｉｎＤＮＡＳｅｑｕｅｎｃｉｎｇ［Ｒ］．Ｔｈｅ５ｔｈＡｎ—
ｎｕａｌ
Ｉｎｔ’ｌ
Ｃｏｎｆ
Ｏｎ
设最终形成的Ｃｏｎｓｅｎｓｕｓ序列长度为ｈ，每个片段处理
Ｃｏｍｐｕｔａｔｉｏｎａｌ
Ｍｏｌｅｃｕｌａｒ
Ｂｉｏｌｏｇｙ
（ＲＥＣＯＭＢ２００１）［Ｃ］．２００１．时问平均为Ｚ
，则
［３］Ｇ
ＧＳｕｔｔｏｎ，０
ｗｈｉｔｅ，ＭＤＡｄｍａｓ，ｅｔａ１．ＴＩＧＲＡｓｓｅｍｂｌｅｒ：Ａ
本阶段串行处理过程的执行时间为竹Ｚ
。
ＮｅｗＴｏｏｌｆｏｒＡｓｓｅｍｂｌｉｎｇＬａｒｇｅＳｈｏｔｇｕｎＳｅｑｕｅｎｃｉｎｇＰｒｏｊｅｃｔｓ
并行算法执行时间等于通信时间瓦一加上计算时间
Ｉ－Ｊ］．Ｇｅｎｏｍｅ
ＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，１９９５，１（１）：９－１９．
了’。巾，丁。脚为，２Ｔ一／（ｍ＋１），Ｌ一为２ｋｍＬ。＋（行＋＾）Ｉ－４－１
ＸｉａｏｑｉｕＨｕａｎｇ，ＧｌｅｎＨｅｒｒｍａｎｎｓｆｅｌｄｔ，ＴｅｄＪｏｎｅｓ，ｅｔａＬＣＡＰ４一
了乙。，因此并行算法执行时间为Ｌ一＋了■，一２ｋｍＴ刍＋
Ｐａｒａｃｅｌ’ＳＤＮＡＳｅｑｕｅｎｃｅＡｓｓｅｍｂｌｙ
Ｐｒｏｇｒａｍ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／
（行＋＾）Ｔｋ＋挖ｚ
加速比为竹ｋ。／（２ｋｍＬ。＋（”＋ｈ）死。＋
；／（ｍ＋１）。
、＾Ｈ吼ｐａｒａｃｅｌ．ｃｏｍ，２０００－０９．
［５］
张法，刘志勇，乔香珍，等．生物序列拼接算法一ＰＨＲＡＰ的卵ｚ
／（ｍ十１））。
并行化研究［Ｒ－Ｉ．第七届全国并行计算年会，２００２．［６］杨金水．基因组学［Ｍ］．北京：高等教育出版社，２００２．４数值试验
［７］Ｘ
Ｈｕａｎｇ，Ａ
ＭａｄａｍＣＡＰ３：ＡＤＮＡＳｅｑｕｅｎｃｅＡｓｓｅｍｂｌｙＰｒｏ—
ｇｒａｍＥＪ］．Ｇｅｎｏｍｅ
Ｒｅｓｅａｒｃｈ，１９９０，９（９）：８６８—８７７．
我们在８节点的分布式存储并行计算环境下进行了本文算法的数值试验，测试环境见表１。
我们对两个片段数目分别为５０００和７０００的数据集进行了测试，结果如表２，其中绐出的时间为主节点完成所
有数据处理的运行时间。
万
方数据７７
DNA序列拼接的分布式并行处理
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
方小永， 骆志刚
并行与分布处理国家重点实验室,湖南,长沙,410073计算机工程与科学
COMPUTER ENGINEERING AND SCIENCE2005,27(2)3次
参考文献(7条)
1. P Green Documentation for Phrap 2003
2. P A Pevzner;Haixu Tang;M S Waterman A New Approach to Fragment Assembly in DNA Sequencing[外文会议] 2001
3. G G Sutton;O White;M D Admas TIGR Assembler:A New Tool for Assembling Large Shotgun SequencingProjects 1995(01)
4. Xiaoqiu Huang;Glen Herrmannsfeldt;Ted Jones CAP4-Paracel's DNA Sequence Assembly Program 20005. 张法;刘志勇;乔香珍 生物序列拼接算法-PHRAP的并行化研究 20026. 杨金水 基因组学 2002
7. X Huang;A Madan CAP3:A DNA Sequence Assembly Program 1990(09)
本文读者也读过(10条)
1. 蔡毅. 骆志刚 DNA序列拼接算法分析及并行化探讨[会议论文]-2008
2. 张法. 刘志勇. 乔香珍. 刘玮 生物序列拼接算法--phrap的并行化研究[会议论文]-2003
3. 骆志刚. 方小永. 丁凡. LUO Zhi-gang. FANG Xiao-yong. DING Fan DNA序列拼接的研究进展及挑战[期刊论文]-计算机工程与科学2007,29(8)
4. 方小永 DNA序列拼接的分布式并行处理[学位论文]2003
5. 郑纬民. 林皎. 罗水华 基于欧拉超路的并行DNA序列拼接算法[会议论文]-2003
6. 郑纬民. 林皎. 罗水华. ZHENG Wei-Min. LIN Jiao. LUO Shui-Hua DNA序列拼接中欧拉超路算法的新并行策略[期刊论文]-计算机学报2006,29(1)
7. 张法. 陈子阳. 刘玮 MPI+OpenMP在生物序列拼接算法phrap并行化中的应用[会议论文]-20028. 蔡葵 DNA片段拼接中的重复序列预归并方法研究[学位论文]2009
9. 李小妹. 王能超. LI Xiao-mei. WANG Neng-chao 序列拼接中重复子串屏蔽的KMP算法[期刊论文]-小型微型计算机系统2006,27(2)
10. 涂俐兰. 王能超 DNA序列拼接中重复序列屏蔽的一种新方法[期刊论文]-华中科技大学学报(自然科学版)2004,32(8)
引证文献(4条)
1. 欧阳继超. 冯萍. 康继昌 超长DNA序列的高效压缩算法研究[期刊论文]-计算机技术与发展
2013(12)
2. 金毅 基于网格的信息模型的研究与应用[学位论文]硕士 2006
3. 毛逸清. 赵东升. 李稚锋. 杭兴宜. 骆志刚. 张成岗 大规模EST序列聚类的并行算法研究进展[期刊论文]-军事医学科学院院刊 2006(6)
4. 骆志刚. 方小永. 丁凡 DNA序列拼接的研究进展及挑战[期刊论文]-计算机工程与科学 2007(8)
本文链接：http://d.wanfangdata.com.cn/Periodical_jsjgcykx200502027.aspx
ＣＮ４３—１２５８／ＴＰ
计算机工程与科学
２００５年第２７卷第２期
ＩＳＳＮ１００７—１３０Ｘ
ＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩ￡ＮＣＥ
Ｖ０１．２７，Ｎｏ．２，２００５
文章编号：１００７－１３０Ｘ（２００５）０２－００７１－０３
ＤＮＡ序列拼接的分布式并行处理。
ＡＤｉｓｔｒｉｂｕｔｅｄＰａｒａｌｌｅｌＡｌｇｏｒｉｔｈｍｆｏｒＤＮＡ
Ｓｅｅｌ｝ｕｅｎｃｅＵｅｎｃｅｌｂｍｅｓｓＡ
ｓｅ
厂
方小永。骆志刚
ＦＡＮＧＸｉａｏ－ｙｏｎｇ。ＬＵＯＺｈｉ－ｇａｎｇ
（并行与分布处理国家重点实验室，湖南长沙４１００７３）
（Ｎａｔｉｏｎａｌ
Ｌａｂｏｒａｔｏｒｙ
ｆｏｒＰａｒａｌｌｅｌａｎｄＤｉｓｔＨｂｕｔｅｄＰｒｏｃｅｓｓｉｎｇ－Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ）
摘要：针对分布式存储环境，本文提出一种ＤＮＡ序列拼接的并行算法，分别对序列拼接中ＯＶＥＲＬＡＰ、ＬＡＹＯＵＴ
和ＣＯＮＳＥＮＳＵＳ阶段的串行处理过程和并行算法进行了描述，并给出了算法复杂性分析。数值试验结果表明，算法是高
效的。
Ａｂｓｔｒａｃｔ：ＡｎｏｖｅｌｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｆｏｒＤＮＡｓｅｑｕｅｎｃｅａｓｓｅｍｂｌｙｕｎｄｅｒｔｈｅｄｉｓｔｒｉｂｕｔｅｄｍｅｍｏｒｙ
ｅｎｖｉｒｏｎｍｅｎｔｉｓｐｒｅｓｅｎｔｅｄ
ｉｎｔｈｉｓｐａｐｅｒ．Ｔｈｅｓｅｒｉａｌｐｒｏｃｅｓｓｉｎｇｐｒｏｃｅｄｕｒｅａｎｄｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍ
ｆｏｒＯＶＥＲＬＡＰ，ＬＡＹｏＵＴａｎｄＣＯＮＳＥＮＳＵＳｏｆｔｈｅ
ＤＮＡｓｅｑｕｅｎｃｅａｓｓｅｍｂｌｙａｒｅｄｅｓｃｒｉｂｅｄ
ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｔｈｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅ
ａｌｇｏｒｉｔｈｍ
ｉｓａｎａｌｙｚｅｄ．Ｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔ
ｔｈｉｓ
ａｌｇｏｒｉｔｈｍｉｓ
ｏｆ‘
ｈｉｇｈｅｆｆｉｃｉｅｎｃｙ．
关键词：生物信息；序列拼接；并行处理；分布式
Ｋｅｙｗｏｒｄｓ：ｂｉｏｉｎｆｏｒｍａｔｉｃｓ；ｓｅｑｕｅｎｃｅａｓｓｅｍｂＩｙ；ｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍ；ｄｉｓｔｒｉｂｕｔｅｄｍｅｍｏｒｙ
中图分类号：Ｑ８１１．４文献标识码：Ａ
１
引言
和Ⅱ几ＥＲ［引。此外，还有其它一些各有特点的拼接算法，如ＴＩＧＲ｛３］、ＣＡＰ４［４］等。ＤＮＡ序列拼接在存储和时间开基因组计划的目标是获得所研究的生物的全基因组序
销上都非常巨大。例如，ＰＨＲＡＰ在对规模为１０００００条列，而序列拼接是基因组测序阶段生物信息学研究的最基ｒｅａｄ的螺旋藻序列进行拼接时，所需要的内存空间将达到本、最重要的问题。众所周知，生物的基因组是指该生物所６Ｇ，在曙光３０００上耗时８６５１７．２５９２秒，约合２４小时［５］。有遗传物质的总和，绝大部分基因组由ＤＮＡ（脱氧核糖核因而，ＤＮＡ序列拼接并行处理的研究有着理论和现实的重酸）组成。ＤＮＡ是由核苷酸单体构成的线性、无分支的多要意义。这方面国外较著名的是ＳＰＳＯＦＴ（ｈｔｔｐ：／／ｗｗｗ．聚分子。核苷酸由碱基区分，ＤＮＡ中，碱基分别是腺嘌呤ｓｐｓｏｆｔｃｏｒｎ），国内中科院计算所智能信息处理实验室在曙（Ａｄｅｎｉｎｅ）、胞嘧啶（Ｃｙｔｏｓｉｎｅ）、鸟嘌呤（Ｇｕａｎｉｎｅ）和胸腺嘧光３０００上实现了ＰＨＲＡＰ的并行化［５］。
啶（Ｔｈｙｍｉｎｅ），分别用字母Ａ、Ｃ、Ｇ、Ｔ表示。基因组测序就本文提出分布式存储环境下进行ＤＮＡ序列拼接的一是要确定ＤＮＡ分子的碱基序列。由于基因组的每条染色种新的并行算法，这是基于Ｈａｍｉｌｔｏｎ图的一类拼接方法。体长度可达数百万碱基对以上，而按目前的测序技术，一次我们将首先给出算法的推导过程和描述，然后对算法复杂实验最多只能直接测得不大于７５０个碱基，因此一个长的性进行分析并给出算法的性能评估。
ＤＮＡ分子序列只能通过将一系列短序列拼接起来而得到。将基因组测序得到的上千万个小片段序列通过比对再正确２算法
拼接起来，就是ＤＮＡ序列拼接和组装所要解决的问题。
目前，ＤＮＡ序列拼接算法可以分为两类，它们分别基２．１
ＤＮＡ序列拼接问题的描述
于Ｈａｍｉｌｔｏｎ图和Ｅｕｌｅｒ图，最具代表的分别是ＰＨＲＡＰ［１］
目前，主要的基因测序方法有鸟枪法、克隆重叠群法和
・
收稿日期：２００３－０８－２５；修订日期：２００３－１０－３０
作者简介：方小永（１９７８一），男，河南汝南人，硕士生，研究方向为生物信息处理；骆志刚，博士，教授，研究方向为生物信息学和高性能并行计算。
通讯地址：４１００７３湖南省长沙市砚瓦池正街４７号并行与分布处理国家重点实验室；Ｔｅｌ：（０７３１）４５７３６６６；Ｅ－ｍａｉｌ：ｘｙｆａｎｇｎｕｄｔ＠
１６３．ｅｏｍ
Ａｄｄｒｅｓｓ：ＮａｔｉｏｎａｌＬａｂｏｒａｔｏｒｙｆｏｒＰａｒａｌｌｅｌａｎｄＤｉｓｔｒｉｂｕｔｅｄＰｒｏｃｅｓｓｉｎｇ，４７ＹａｎｗａｃｈｉＳｔ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ
４１００７３，Ｐ．ＲＣｈｉｎａ
万
方数据７】
定向鸟枪法［６］。无论何种方法，都需要将ＤＮＡ分子（或其长片段）先经过克隆形成若干个拷贝，将这些拷贝打碎成若干条短的、可以直接测序的片段（称为Ｒｅａｄ）。这些Ｒｅａｄ之间存在着大小不等的重叠（Ｏｖｅｒｌａｐ）区域。ＤＮＡ序列拼接就是要通过这些Ｒｅａｄ重新构造出原始的ＤＮＡ序列。
２．２算法的推导和描述
基于Ｈａｍｉｌｔｏｎ图方法的基本思想是［７］：首先将所有的Ｒｅａｄ构成一个有向图Ｇ，每个Ｒｅａｄ看成一个结点，如果两个ｒｅａｄ之间存在有重叠，那么在相应的结点之间就存在有一条边；然后，通过寻找经过每个Ｒｅａｄ一次且仅一次的一条路径，就将序列拼接问题转化成Ｈａｍｉｌｔｏｎ路经问题。这种方法可以分为如下三步：（１）找出序列片段间的重叠信息；（２）将存在有重叠的片段组合起来，形成一个Ｃｏｎｔｉｇ结构；（３）根据片段中每个碱基的质量值，在Ｃｏｎｔｉｇ结构中寻找一条最终序列，称作“Ｃｏｎｓｅｎｓｕｓ”序列。
基于Ｈａｍｉｌｔｏｎ图方法的拼接算法分以下三个阶段：
（１）ＯＶＥＩ也ＡＰ，对所有的片段进行两两比对，以获得可能存在的重叠部分的信息；
（２）ＬＡＹＯＵＴ，根据得到的重叠信息将存在重叠的片
段建立一种组合关系，形成一个链接体，称作“Ｃｏｎｔｉｇ”；
（３）ＣＯＮＳＥＮＳＵＳ，根据构成链接体Ｃｏｎｔｉｇ的片段的
原始质量数据，在链接体中寻找一条质量最重的序列路径，
并获得与路径相对应的序列，称作“Ｃｏｎｓｅｎｓｕｓ”序列。
本文算法的描述过程是，首先给出上述每一阶段的串行处理过程，然后给出本步的并行算法描述。算法描述中
处理机设为ｍ＋１个，记为Ｐ０，Ｐ１，．一，Ｒ。
２．２．１
ＯＶＥＲＬＡＰ
两个片段可以拼接的必要条件是这两个片段之间存在一个重叠部分ｏｖｅｒｌａｐ，并且在重叠部分有一个最小长度为ｍｉｎ＿ｚｏｏｒｄ的精确匹配区域ｍａｔｃｈ。如果ｍａｔｃｈ的长度超过ｎ“２ｘ＿ｗｏｒｄ，则认为这两个片段是几乎相同的而不适合拼接。因此，算法首先需要找出所有满足条件的片段对（称
为ＲｅａｄＰａｉｒ）［１］。另外，如果两个片段可以进行拼接，那么
只有那些首、尾相接的ＲｅａｄＰａｉｒ才有意义，否则由于口ｖｅｒｌａｐ长度太长，可以认为两个片段是同一条序列。因此可以设置一个参数ｍａｘ—ｏｖｅｒｌａｐ，首先把每个片段划分为首、尾两部分（对于那些长度较短的片段，首、尾可以重叠），然后只需拿一个片段的首或尾与另一个片段的尾或首进行比对即可。
找出所有满足上述条件的ＲｅａｄＰａｉｒ后，通过序列比对算法Ｓｍｉｔｈ－Ｗａｔｅｒｍａｎ来精确计算每个ＲｅａｄＰａｉｒ可能存在
的Ｏｖｅｒｌａｐ，并对每一个可能的ｏｖｅｒｌａｐ计算Ｓｍｉｔｈ－Ｗａｔｅｒ—
ｍａｎ得分Ｓｃｏｒｅ，如果Ｓｃｏｒｅ大于ｒａｉｎ—ｓｃｏｒｅ则认为Ｏｖｅｒ—ｌａｐ，否则不予接受。另外，为了提高拼接的准确度，需要对每个Ｏｖｅｒｌａｐ采用ＬＬＲ（ＴｈｅＬａｒｇｅｓｔＬｉｋｅｌｉｈｏｏｄＲａｔｉｏ，简称ＬＬＲ）进行打分［１］，如果该Ｏｖｅｒｌａｐ的ＬＬＲ大于０，则认
为是真Ｏｖｅｒｌａｐ，否则不予接受。
这一部分的串行处理过程描述如下：
输入：片段集合卜｛ｆｏ，＾，…，＾一１｝。
输出：Ｏｖｅｒｌａｐ集合Ｏ一｛Ｏ（五，乃）Ｊ五，力∈ｒ，且＾和乃存在Ｏｖｅｒｌａｐ｝；包含Ｏｖｅｒｌａｐ的Ｃｏｎｔｉｇ集合ｔ＇２一｛Ｃ１，Ｃ２，…，Ｇ｝。
参数：ｍｉｎ＿＿ｗａｒｄ：可接受的ｍａｔｃｈ的最小长度；ｍ∞一ｗｏｒｄ：可接
７２
万
方数据受的ｍａｔｃｈ的最大长度；ｒａｉｎ＿ｓｃｏｒｅ：可接受的Ｏｖｅｒｌａｐ的最小Ｓｍｉｔｈ－
Ｗａｔｅｒｍａｎ得分；ｍａｘ＿ｏｖｅｒｌａｐ：可接受的Ｏｖｅｒｌａｐ的最大长度。
Ｓｔｅｐｌ：若１１中尚未进行比对的片段不少于两个，则从＿ｒ中任意取两个片段：，ｉ，五。
Ｓｔｅｐ２：依据ｍａｘ＿ｏｖｅｒｌａｐ参数，分别把五和兀分为首、尾两部分；比较五的首和乃的尾，比较五的尾和＾的首；找出五和力
中所有满足条件“长度在ｒａｉｎ—ｚｏｏｒｄ和一一ｗｏｒｄ范围内”的ｍａｔｃｈ；若在五和＾中存在满足条件的ｍａｔｃｈ，则转Ｓｔｅｐ３，否则转
Ｓｔｅｐｌ。
Ｓｔｅｐ３：对Ｓｔｅｐ２得到的每一个ｍａｔｃｈ，首先要覆盖整个重叠区域（可能不是精确匹配）；然后对整个重叠区域实施Ｓｍｉｔｈ—Ｗａｔｅｒ－
ｍａｎ算法，以精确寻找，ｆ和＾之间存在的Ｏｖｅｒｌａｐ，并计算该ｐ
ｖｅｒｌａｐ的Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ得分；取Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ得分最高的
那个ｍａｔｃｈ覆盖的重叠区域作为Ｏｖｅｒｌａｐ，并把其Ｓｍｉｔｈ—Ｗａｔｅｒ—
ｍａｒｌ得分记为Ｓｃｏｒｅ（五，乃）。
’
Ｓｔｅｐ４：若Ｓｃｏｒｅ（五，五）小于ｍｉｎ—ｓｃｏｒｅ，则转Ｓｔｅｐｌ，否则转
Ｓｔｅｐ５。
Ｓｔｅｐ５：对Ｏｖｅｒｌａｐ利用Ｓｍｉｔｈ—Ｗａｔｅｒｍａｎ算法进行回溯，并计算每条回溯路径下的Ｌ上瓜，以寻找五和＾的最佳对齐方式（ａｌｉｇｎ—
ｍｅｎｔ）。
Ｓｔｅｐ６：取ＬＬＲ最高的那个ａｌｉｇｎｍｅｎｔ作为Ｏｖｅｒｌａｐ（，ｆ，ｆＪ），然后把Ｏｖｅｒｌａｐ（，ｆ，ｆＪ）输出到相应的Ｃｏｎｔｉｇ，并保存相应的重叠信息，然后转Ｓｔｅｐｌ执行；该操作中Ｃｏｎｔｉｇ是动态创建的，并且依据
输出的Ｏｖｅｒｌａｐ动态合并。
在本阶段，我们需要对佗条片段两两比对以寻找０一ｖｅｒｌａｐ，即每个片段需要和其它片段比对以寻找Ｏｖｅｒｌａｐ。因此，我们只要对全体片段数据进行正确分割，每个片段就可以独立执行比对操作，可以并行处理。我们的做法是：把本阶段全体片段数据比对操作总量分为ｍ＋１组，分别分派给ｍ＋１个处理机执行。为保持负载平衡，我们在任务分派时对全体片断数据进行动态分割。
并行算法描述如下：
输入、输出及参数设置同本阶段的串行处理过程；
设布尔变量ｃｏｎｔｒｏｌ控制算法对数据进行动态分割，初始为
ｔｒｕｅ；
Ｓｔｅｐｌ：Ｐ０作如下操作：
（１）Ｆｏｒ（ｉ＝０；ｉ＜ｎ－－１；）
｛
Ｆｏｒ（ｊ＝ｉ＋１；ｊ＜ｎ；ｊ＋＋）
｛对五，五执行本阶段串行处理过程Ｓｔｅｐ２～
Ｓｔｅｐ６｝；
ｉｆ（ｃｏｎｔｒ０１）
｛ｃｏｎｔｒｏｌ＝ｆａｌｓｅ；
ｉ—ｉ＋２（ｍ＋１）一１；｝
ｅｌｓｅ
｛ｃｏｎｔｒｏｌ＝ｔｒｕｅ；ｉ＝ｉ＋１；）
｝
（２）Ｆｏｒ（ｉ＝１；ｉ＜ｍ＋１；ｉ＋＋）
｛接收Ｐｉ（１≤ｉ≤ｍ）的处理结果数据包并解包；｝
（３）处理Ｐｏ，Ｐ１，…，Ｐ０１的执行结果以形成Ｃｏｎｔｉｇ集合
ｎ，终止程序执行；
Ｓｔｅｐ２：Ｂ（１≤女≤ｍ）作以下操作：
（１）Ｆｏｒ（ｉ＝ｋ；ｉ＜ｎ一１；）
｛
Ｆｏｒ（ｊ—ｉ＋１；ｊ＜ｎ；ｊ＋＋）
｛对五，五执行本阶段串行处理过程Ｓｔｅｐ２～
Ｓｔｅｐ６｝；
ｉｆ（ｃｏｎｔｒ０１）
｛ｃｏｎｔｒｏｌ＝ｆａｌｓｅ；
ｉ—ｉ＋２（ｍ＋１）一（２ｋ＋１）；｝
ｅｌｓｅ
｛ｃｏｎｔｒｏｌ＝ｔｒｕｅ；ｉ＝ｉ＋（２ｋ＋１）；｝｝
（２）对执行结果进行打包并发送给Ｐ０；
２．２．２
ＬＡＹＯＵＴ
若片段工和＾存在重叠区域，则称厂ｆ和＾直接相关；若片段五与片段＾直接相关，片段正与片段＾直接
相关，片段＾与片段＾不直接相关，则称片段五与片段＾间接相关。
输出Ｃｏｎｓｅｎｓｕｓ序列。为保证精度，每个片段在投票前需
对其质量值进行修正，修正的依据是该片段保存的重叠区域信息。由于片段间的投票操作是彼此独立的，因此可以并行处理。
这一部分的串行处理过程描述如下：
输入：计算所有片段偏移量以后的Ｃｏｎｔｉｇ集合１２＝｛ｃ１，Ｑ，…，Ｑ｝；与每个Ｃｏｎｔｉｇ对应的片段集合ｎ，ｎ，…，ｎ。
输出：与每个Ｃｏｎｔｉｇ对应的ｃｏｎｓｅｎｓｕｓ序列Ｓ１，Ｓｚ，…，＆。操作：处理ｎ中的每个Ｃｏｎｔｉｇ。对每个Ｃｏｎｔｉｇ，设它包含的所有片段按照其偏移量从小到大依次排列为：，０，＾，…，＾，记为，一｛，０，＾，…，＾）。则对每个Ｃｏｎｔｉｇ，作以下操作：
Ｓｔｅｐｌ：若，不空，则从首位置取下一个片段五。
Ｓｔｅｐ２：依据ＯＶＥＲＬＡＰ阶段保存的重叠信息对，ｆ的碱基字符排列和质量值进行修正，使得五的质量值最大。
在ＯＶＥＲＬＡＰ阶段，我们在输出Ｏｖｅｒｌａｐ时，要求Ｏｖｅｒ－
ｌａｐ输出到相应的Ｃｏｎｔｉｇ，即把所有具有直接相关或间接相关关系的片段汇集在同一Ｃｏｎｔｉｇ里，这些里的片段最终将形成一个ｃｏｎｓｅｎｓｕｓ序列Ｓ。为此，需要计算每一条片段相对于Ｓ起始位置的偏移量。我们需要分别对每个Ｃｏｎｔｉｇ包含的片段计算其偏移量以决定片段间的组合关系。
这一部分的串行处理过程描述如下：
输入：包含Ｏｖｅｒｌａｐ的Ｃｏｎｔｉｇ集合１２＝｛Ｃａ，ｃ２，…，Ｇ）；
输出：计算所有片段偏移量以后的Ｃｏｎｔｉｇ集合ｎ＝｛ｃ１，Ｃ２，
…，Ｑ｝；
操作：处理ｎ中的每个Ｃｏｎｔｉｇ；对每个Ｃｏｎｔｉｇ，作以下操作：
Ｓｔｅｐｌ：对该Ｃｏｎｔｉｇ包含的Ｏｖｅｒｌａｐ按照ＬＬＲ以降序排列，并删除那些ＬＬＲ小于０的Ｏｖｅｒｌａｐ（因为这样的Ｏｖｅｒｌａｐ不适合拼接）。
Ｓｔｅｐ２：取下ＬＬＲ最高的那个Ｏｖｅｒｌａｐ（＾，ｆＪ）。若五的起始位
置在，ｉ的左端，则取五的起始位置为参考原点，否则取力的起始位置为参考原点。
Ｓｔｅｐ３：处理该Ｃｏｎｔｉｇ包含的每个Ｏｖｅｒｌａｐ（五，五），即计算五，乃
相对于参考原点的偏移量（若片段的起始位置在参考原点左端，则偏移量为负，否则为正）；包含参考原点的那个片段的偏移量为０。
Ｓｔｅｐ４：取偏移量最小的那个片段的起始位置为参考原点，并把该片段的偏移量取为Ｏ；依据新的参考原点，修正所有片段的偏移量。
在本阶段，由于各个Ｃｏｎｔｉｇ彼此独立，我们采用工作池的动态任务分派方法将其并行化。
’
并行算法描述如下：
输入、输出及参数设置同本阶段串行处理过程。
设参数ｃｏｕｎｔ表示已经处理完毕的Ｃｏｎｔｉｇ数目，初始为０。Ｓｔｅｐｌ：Ｐｏ作如下操作：
（１）从ｎ中取出ｒｎ个Ｃｏｎｔｉｇ：Ｃｘ，Ｃｚ，…，．Ｃｋ，分别发送给Ｐ１，
Ｐ２，…，Ｐｍ；ｃｏｕｎｔ一０；０＝／２－－｛Ｃｌ，Ｑ’．．・，Ｇ｝。
（２）如果ｎ不空，则从ｎ中取出一个Ｃｏｎｔｉｇ：Ｇ（１≤ｉ≤＾）；对ｃｆ执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ４，ｌ＂２＝０－－｛Ｇ｝，∞勰￡增
１。
（３）接收Ｐｉ（１≤ｆ≤ｍ）的处理结果，ｃｏｕｒⅡ增１。
如果ｎ不空，则从０中取出一个Ｃｏｎｔｉｇ：Ｃ／（１≤ｉ≤屉）发送给Ｂ，ｎ＝ｎ一｛ｃｉ），否则通知Ｐｆ终止执行。
（４）如果ｃｏｕｒｔ等于五，则终止执行，否则转（２）执行。Ｓｔｅｐ２：Ｐｆ（１≤ｉ≤ｍ）作以下操作：（１）接收来自Ｐ０的Ｃｏｎｔｉｇ数据ｃｆ；
（２）对ｃ｝执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ４；（３）发送处理结果给Ｐｏ，转（１）执行。
需要指出的是，若Ｃｏｎｔｉｇ个数忌小于处理机个数ｍ＋１，会出现某些处理机空闲的情况。但是，由于相对总计算量而言，本阶段的计算量非常小，对整体并行效率影响不大。
２．２．３
ＣＯＮＳＥＮＳＵＳ
ＤＮＡ序列拼接程序的输入文件有两个，一个是序列文件（ＳｅｑｕｅｎｃｅＦｉｌｅ），另一个是与序列文件对应的质量文件
（ＱｕａｎｌｉｔｙＦｉｌｅ）。序列文件包含将要进行拼接的片段数据
（Ｒｅａｄ），质量文件包括与序列文件中每个片段中每个碱基对应的质量值数据（ＱｕａｌｉｔｙＶａｌｕｅ）。所谓一个碱基的质量值口是指该碱基的可信度大小，它与该碱基测序错误概率Ｐ的关系［１３为：
ｑ一一１０ｌｏｇ（ｐ）
由此可知，Ｐ越小，ｑ就越大，该碱基的可信度就越大。一个片段的质量值是指该片段上所有碱基质量值之和，ＣＯＮＳＥＮＳＵＳ阶段的最终目的就是寻找一条质量值最大的Ｃｏｎｓｅｎｓｕｓ序列。
我们采取每个片段分别对Ｃｏｎｓｅｎｓｕｓ序列投票的方法
万
方数据Ｓｔｅｐ３：执行＾的投票操作：首先依据五的偏移量定位＾在ｃｏｎｓｅｎｓｕｓ序列Ｓ上的起始位置ＢｅｇｉｎＰｏｓｉｔｉｏｎ和结束位置ＥｎｄＰｏｓｉｔｉｏｎ；对于Ｓ上从ＢｅｇｉｎＰｏｓｉｔｉｏｎ到ＥｎｄＰｏｓｉｔｉｏｎ的每一个位置，把，ｆ在该位置上的某种类型的碱基（Ａ、Ｃ、Ｇ、Ｔ之一）质量值都有ａ…ｃ
累加在Ｓ在该位置上的那种类型的碱基质量值上（Ｓ上每个位置
ｇｔ四种类型碱基的质量值累加器，初始值为Ｏ）。Ｓｔｅｐ４：从，删除＾，转Ｓｔｅｐｌ执行，直到，为空。
Ｓｔｅｐ５：对于Ｓ上每个位置输出累加质量值之和最大的那种类型碱基字符，最终输出一条质量值之和最大的一条序列，即ｃｏｉｌ—ｓｅｎ５ｕｓ序列。
对于本阶段算法，Ｃｏｎｔｉｇ之间彼此独立，每一个Ｃｏｎｔｉｇ
内部片段之间的投票操作彼此独立。因此，我们可以顺序
处理每个Ｃｏｎｔｉｇ，对每个Ｃｏｎｔｉｇ可以采用静态任务分配方
法将其并行化。
并行算法描述如下：
输入、输出及参数设置同本阶段串行处理过程。
设参数ｃｏｕｎｔ表示已经处理完毕的Ｃｏｎｔｉｇ数目，其初始为０。Ｓｔｅｐｌ：Ｐｏ作如下操作：
（１）０若不空，则从０中取出一个Ｃｏｎｔｉｇ：Ｇ（１≤ｉ≤志），否则通知Ｐ１，Ｐ２，…，ｆ，卅终止执行。
（２）把ｃ：ｆ包含的片段按偏移量从小到大的顺序依次划分为ｍ
＋１组：ｒ０，ｎ，ｎ，…，Ｌ；把ｎ，ｒ２，…，ｎ分别发送给Ｐ１，Ｐ２，…，
Ｐｍ；１２＝０－－｛ｃｆ｝。
（３）把ｒ０取作，，执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ５。（４）接收Ｐ１，Ｐ２，…，Ｐｋ的执行结果，合并所有处理机的执行结果，ｃｏｕｎｔ增１。
（５）如果ｃｏｕｎｔ等于ｋ，则终止执行，否则转（１）执行。Ｓｔｅｐ２：Ｐｉ（１≤筵；ｍ）作以下操作：
（１）接收来自Ｐｏ的Ｃｏｎｔｉｇ数据中的片段数据ｒｉ（１≤ｉ≤ｍ）。（２）把ｎ取作ｒ’，执行本阶段串行处理过程Ｓｔｅｐｌ～Ｓｔｅｐ５；（３）发送处理结果给Ｐ０，转（１）执行。
３性能分析
设算法要处理咒个片段，产生Ｌ个Ｏｖｅｒｌａｐ，ｋ个Ｃｏｎ－ｔｉｇ，每通信一次所用启动时间为Ｌ。，每发送一个数据所
用时间为Ｔ出。。３．１
ｏＶ腿ＩＡＰ
设每两个片段执行本阶段串行处理过程所用时间平均
为Ｔｒ吲，则：
数为咒（行一１）／２，执行时间为以（咒一１）ｋ／２。
本阶段串行处理过程的计算复杂性为Ｏ（ｎ２），比对次并行算法执行时间等于通信时闳Ｔ—。媳上诗簋赋迥、
了ｋ。。每个处理机分得片段个数为竹／（优＋１），因此Ｔ。巾为（ｎ／（ｍ＋１））（ｎ／（ｍ十１）一１）Ｔｏ／２，Ｌ。。为ＬＴ出。＋
ｍＬ。，并行算法执行时间为Ｌ一十ｋｐ＝（挖／（ｍ＋１））
（ｎ／（ｍ＋１）一１）Ｔ，吲／２＋ＬＴ出。十ｍＴ＃ａ。。
（下转第７７页）
７３
Ｐｒｏｇｒａｍ分别传递ＰｌｏＰ６参数，然后调用程序ＣｏｍｍＰｒｏ—表１测试环境
ｇｒａｍ即可实现ＰｌｏＰ６的功能。封装设计在信息抽象基础上进行描述、提取、加工，最后返回具体的需求结果。这对于大型的信息系统来说，增加业务功能却不增加代码，省去了大量的重复性工作，这一点是有非常好的应用前景的。
参考文献：
［１］李木金，李桔，王光兴．一种基于Ｗｅｂ的网络智能管理模型及
表２测试结果
其实现［Ｊ］．软件学报，１９９９，１０（１１）：１１９１－１１９３．
［２］段海新，杨家海，吴建平．基于Ｗｅｂ和数据库的网络管理系统
的设计与实现［Ｊ］．软件学报，２０００，１１（４）：４６８－４７２．
１（
行）７６８９．０９
１．０００１００［３］侯小梅，毛宗源，张波．基于遗传算法的管理信息系统的智能
串４
１９８９．４０３．８６５９６．６３分解口］．系统工程与电子技术，２０００，２２（１）：５－７．
６１４９５．２１５．１４２８５．７１［４ｑ张文增，孙振国，赵冬斌，等．基于Ｂ／Ｓ结构的实验室管理信
８
１１４８．１７
６．６９７
８３．７１
息系统开发方案ｆＪ］．计算机工程与应用，２００２，３８（１１）：２３２－
２３３．
Ｅ５］路军，王亚东，王晓龙．面向对象的管理信息Ａｇｅｎｔ系统［Ｊ］．
计算机工程与应用，２０００，３６（３）：３０－３２．
１（
行）１３７３１．４０１．０００１００串４
３７６０．２９３．６５２９１＿２９（上接第７３页）
６２４６０．４３５．５８１９３．０１加速比为（，ｚ（竹一１）‰／２）／（（ｎ／（ｍ＋１））（ｎ／（ｍ＋１）一１）
８
２０６９．５４
６．６３５
８２．９４
Ｌ“／２＋ＬＬ‰＋ｍＬ，）ｏ
数值试验结果表明，该算法具有良好的加速比。
３．２
ＬＡＹｏＵＴ
设处理一个Ｏｖｅｒｌａｐ所用时间平均为Ｌ础ｐ，则：
５结束语
本阶段串行处理过程的计算复杂度为０（Ｌ），执行时
目前的拼接算法中，如ＰＨＲＡＰ，某些步骤计算局部性间为Ｌ１ｋ砌。。
不明显，直接并行难度较大。我们在认真分析已有拼接算并行算法执行时间等于最后一个结束计算的处理机法的基础上，结合我们针对的并行处理环境，提出一种新的只（１≤ｉ≤ｍ）与Ｐｏ的通信时间Ｌ一加上最后一个结束计
算的处理机Ｐ，（ｏ≤Ｊ≤ｍ）的计算时间了ｋ，Ｔａ聊为
拼接算法。算法的性能分析和数值试验表明算法是高
效的。
ＬＬ州。／（ｍ＋１），瓦～为２忌Ｔ刍／（ｍ＋１）＋（Ｌ＋竹）Ｔ出。／
（ｍ＋１），因此并行算法执行时间为瓦一＋Ｔａ哪一２ｋＬ。／
（ｍ＋１）＋（Ｌ＋咒）Ｔｋ／（ｍ＋１）＋Ｌ‰。／（ｍ＋１）。参考文献：
Ｉ－１－１
ＰＧｒｅｅｍＤｏｃｕｍｅｎｔａｔｉｏｎｆｏｒＰｈｒａｐ［ＥＢ／ＯＬ－］．ｈｔｔｐ：／／ｂｏｚｅｍ－
＋１）＋Ｌｋ。／（ｍ＋１））。
加速比为Ｌ１ｋ砌，／（２ｋｌｋ。／（ｍ＋１）＋（Ｌ＋ｎ）ｔ‰／（ｍ
ａｍ
ｍｂｔ．ｗａｓｈｉｎｇｔｏｎ．ｅｄｕ／ｐｈｒａｐ．ｄｏｃｓ／ｐｈｒａｐ．ｈｔｍｌ，２００３－０７．
［２］Ｐ
ＡＰｅｖｚｎｅｒ，Ｈａｉｘｕ
Ｔａｎｇ，ＭＳＷａｔｅｒｍａｎ．ＡＮｅｗＡｐｐｒｏａｃｈ
３．３
ＣｏＮＳＥＮＳＵＳ
ｔＯ
ＦｒａｇｍｅｎｔＡｓｓｅｍｂｌｙｉｎＤＮＡＳｅｑｕｅｎｃｉｎｇ［Ｒ］．Ｔｈｅ５ｔｈＡｎ—
ｎｕａｌ
Ｉｎｔ’ｌ
Ｃｏｎｆ
Ｏｎ
设最终形成的Ｃｏｎｓｅｎｓｕｓ序列长度为ｈ，每个片段处理
Ｃｏｍｐｕｔａｔｉｏｎａｌ
Ｍｏｌｅｃｕｌａｒ
Ｂｉｏｌｏｇｙ
（ＲＥＣＯＭＢ２００１）［Ｃ］．２００１．时问平均为Ｚ
，则
［３］Ｇ
ＧＳｕｔｔｏｎ，０
ｗｈｉｔｅ，ＭＤＡｄｍａｓ，ｅｔａ１．ＴＩＧＲＡｓｓｅｍｂｌｅｒ：Ａ
本阶段串行处理过程的执行时间为竹Ｚ
。
ＮｅｗＴｏｏｌｆｏｒＡｓｓｅｍｂｌｉｎｇＬａｒｇｅＳｈｏｔｇｕｎＳｅｑｕｅｎｃｉｎｇＰｒｏｊｅｃｔｓ
并行算法执行时间等于通信时间瓦一加上计算时间
Ｉ－Ｊ］．Ｇｅｎｏｍｅ
ＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，１９９５，１（１）：９－１９．
了’。巾，丁。脚为，２Ｔ一／（ｍ＋１），Ｌ一为２ｋｍＬ。＋（行＋＾）Ｉ－４－１
ＸｉａｏｑｉｕＨｕａｎｇ，ＧｌｅｎＨｅｒｒｍａｎｎｓｆｅｌｄｔ，ＴｅｄＪｏｎｅｓ，ｅｔａＬＣＡＰ４一
了乙。，因此并行算法执行时间为Ｌ一＋了■，一２ｋｍＴ刍＋
Ｐａｒａｃｅｌ’ＳＤＮＡＳｅｑｕｅｎｃｅＡｓｓｅｍｂｌｙ
Ｐｒｏｇｒａｍ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／
（行＋＾）Ｔｋ＋挖ｚ
加速比为竹ｋ。／（２ｋｍＬ。＋（”＋ｈ）死。＋
；／（ｍ＋１）。
、＾Ｈ吼ｐａｒａｃｅｌ．ｃｏｍ，２０００－０９．
［５］
张法，刘志勇，乔香珍，等．生物序列拼接算法一ＰＨＲＡＰ的卵ｚ
／（ｍ十１））。
并行化研究［Ｒ－Ｉ．第七届全国并行计算年会，２００２．［６］杨金水．基因组学［Ｍ］．北京：高等教育出版社，２００２．４数值试验
［７］Ｘ
Ｈｕａｎｇ，Ａ
ＭａｄａｍＣＡＰ３：ＡＤＮＡＳｅｑｕｅｎｃｅＡｓｓｅｍｂｌｙＰｒｏ—
ｇｒａｍＥＪ］．Ｇｅｎｏｍｅ
Ｒｅｓｅａｒｃｈ，１９９０，９（９）：８６８—８７７．
我们在８节点的分布式存储并行计算环境下进行了本文算法的数值试验，测试环境见表１。
我们对两个片段数目分别为５０００和７０００的数据集进行了测试，结果如表２，其中绐出的时间为主节点完成所
有数据处理的运行时间。
万
方数据７７
DNA序列拼接的分布式并行处理
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
方小永， 骆志刚
并行与分布处理国家重点实验室,湖南,长沙,410073计算机工程与科学
COMPUTER ENGINEERING AND SCIENCE2005,27(2)3次
参考文献(7条)
1. P Green Documentation for Phrap 2003
2. P A Pevzner;Haixu Tang;M S Waterman A New Approach to Fragment Assembly in DNA Sequencing[外文会议] 2001
3. G G Sutton;O White;M D Admas TIGR Assembler:A New Tool for Assembling Large Shotgun SequencingProjects 1995(01)
4. Xiaoqiu Huang;Glen Herrmannsfeldt;Ted Jones CAP4-Paracel's DNA Sequence Assembly Program 20005. 张法;刘志勇;乔香珍 生物序列拼接算法-PHRAP的并行化研究 20026. 杨金水 基因组学 2002
7. X Huang;A Madan CAP3:A DNA Sequence Assembly Program 1990(09)
本文读者也读过(10条)
1. 蔡毅. 骆志刚 DNA序列拼接算法分析及并行化探讨[会议论文]-2008
2. 张法. 刘志勇. 乔香珍. 刘玮 生物序列拼接算法--phrap的并行化研究[会议论文]-2003
3. 骆志刚. 方小永. 丁凡. LUO Zhi-gang. FANG Xiao-yong. DING Fan DNA序列拼接的研究进展及挑战[期刊论文]-计算机工程与科学2007,29(8)
4. 方小永 DNA序列拼接的分布式并行处理[学位论文]2003
5. 郑纬民. 林皎. 罗水华 基于欧拉超路的并行DNA序列拼接算法[会议论文]-2003
6. 郑纬民. 林皎. 罗水华. ZHENG Wei-Min. LIN Jiao. LUO Shui-Hua DNA序列拼接中欧拉超路算法的新并行策略[期刊论文]-计算机学报2006,29(1)
7. 张法. 陈子阳. 刘玮 MPI+OpenMP在生物序列拼接算法phrap并行化中的应用[会议论文]-20028. 蔡葵 DNA片段拼接中的重复序列预归并方法研究[学位论文]2009
9. 李小妹. 王能超. LI Xiao-mei. WANG Neng-chao 序列拼接中重复子串屏蔽的KMP算法[期刊论文]-小型微型计算机系统2006,27(2)
10. 涂俐兰. 王能超 DNA序列拼接中重复序列屏蔽的一种新方法[期刊论文]-华中科技大学学报(自然科学版)2004,32(8)
引证文献(4条)
1. 欧阳继超. 冯萍. 康继昌 超长DNA序列的高效压缩算法研究[期刊论文]-计算机技术与发展
2013(12)
2. 金毅 基于网格的信息模型的研究与应用[学位论文]硕士 2006
3. 毛逸清. 赵东升. 李稚锋. 杭兴宜. 骆志刚. 张成岗 大规模EST序列聚类的并行算法研究进展[期刊论文]-军事医学科学院院刊 2006(6)
4. 骆志刚. 方小永. 丁凡 DNA序列拼接的研究进展及挑战[期刊论文]-计算机工程与科学 2007(8)
本文链接：http://d.wanfangdata.com.cn/Periodical_jsjgcykx200502027.aspx