文摘
解码基因组序列,鸟枪测序是最先进的技术。它需要正确的序列一个非常大的数字,有时多达数百万,短部分可读的字符串(片段)。安排这些碎片在正确的顺序被称为片段组装,这是一个np问题。目前使用的方法需要巨大的计算成本。在这项工作中,我们已经表明我们的改进遗传算法(GA)可以有效地解决这个问题。提出了GA,染色体的长度,代表搜索空间的体积与推进代减少,从而提高了搜索效率。附近我们还引入了一个贪婪的突变,通过交换使用一些启发式的碎片,提高健身的染色体。我们比较结果与帕森斯的算法基于GA。我们使用与两侧部分读取片段,模仿实际基因组片段组装过程。在帕森斯的工作碱基对的整个片段。 Even then, we could obtain much better results, and we succeeded in restructuring contigs covering 100% of the genome sequences.
1。介绍
1.1。基因是什么?
生物信息学的研究是最具活力的研究领域之一,其重要的应用是呈指数级增长。一个好的起点是尼尔和帕维尔的入门书1]。各种有趣的应用报告,计算算法起着重要的作用,(2,3]。所有的生物信息学研究,基因组测序得到高度重视从本世纪初,从人类基因组(4),测序的作物(5]。
基因组的完整基因序列由四种元素的字母表,腺嘌呤(A)、胸腺嘧啶(T)、胞嘧啶(C)和鸟嘌呤(G),字母A T、C、G代表被称为核苷酸分子或基地。在活细胞中,它出现在一个双螺旋结构6]。每个基地一分之一链是搭配了一个T链,每个基地C是同样与g .这些对被称为碱基对,或者仅仅是英国石油公司(7,8]。
基因(DNA)从几千核苷酸序列是非常长的小病毒超过3 gb核苷酸对人类。基因组的小麦(英国石油公司)和莉莉(bp)超过人类基因组(从NCBI数据库(国家生物技术信息中心-http://www.ncbi.nlm.nih.gov/))。显然,破译他们,虽然重要,但很复杂。
1.2。为什么它是重要的破译DNA序列?
负责生产不同的蛋白质,DNA序列是一个活的有机体的功能的根源。因此解码基因组序列的第一步了解生物的功能以及故障,医学,农业,和许多其他的研究领域。人类基因组的调查可能会导致遗传性疾病的原因,医学治疗各种疾病的发展。基因组分析有助于提高作物的育种。此外,它是在进化生物学信息调查的关键。希望鸭嘴兽基因组,这是最近2008年解码,将为深入比较分析提供有价值的资源的哺乳动物(9]。
1.3。现有片段组装方法
桑格测序(10)方法是众所周知的和最常用的阅读基因组序列。它使用凝胶电泳促进阅读基地由于反应的荧光染料染色不同的基地是不同的。但可以读只有几百碱基对。要解决这个问题,目标基因克隆到副本和切成小的片段。基地的那些片段阅读和原来的基因组序列组装使用的信息重叠的部分片段。这个过程被称为鸟枪测序和基因组测序(是最常用的方法11- - - - - -13]。事实上,着陆器et al。4),使用猎枪测序,最初的人类基因组的测序≈在2001年3.5 Gbps的长度。
大多数现有的片段组装系统读取片段的碱基序列桑格与他们的专有技术和重建原来的基因组序列组装算法。许多装配算法提出了,重要的是TIGR汇编[14],拉面[15],塞莱拉汇编[16],CAP3 [17],Phrap [18]。重建目标基因,需要大量的碎片和组装到正确的序列是一个np难问题。
1.4。基于遗传基因组片段组装工作
目前的工作是基于遗传算法(GA),修改是有效的阵列组装问题。在近十年来一些作品被报道使用遗传算法或类似的技术聚类算法和模式匹配算法解决片段组装问题。调查与比较各自的表演是由李和Khuri19]。大多数基于GA的作品简单修改帕森斯等人的作品(20.]。近期作品(21,22使用分布式遗传算法。方等的工作(23也是基于标准遗传算法,但他们用玩具很小的基因组100个碱基对长度的问题。我们工作的主要区别和其他基于GA的作品发表在碎片的定义。帕森斯使用的碎片的碱基对和其他人的工作完全阅读。他们用GenFrag [24)来生成这样的片段。在现实中,通过Sagner技术,我们可以阅读只有一小部分两边的片段。在我们的实验(包括我们以前的工作25])碱基对的一小部分,只有两端的片段,是已知的。因此我们处理问题更现实的和困难的情况相比的碱基对序列片段。此外,由于使用这样的片段,我们可以意识到脚手架在我们提出的方法。
一些确定性算法,提出了基于图论和贪婪启发式算法。但是他们非常涉及计算,需要大规模并行处理的计算环境这是非常昂贵的。全世界只有几个这样的装置是可用的,他们属于大型的研究设施。然而,基因组测序的需要越来越强烈的感受到在每一个小的医学研究中心,药物开发中心、农业研究中心,等等。帮助发展他们的研究我们需要一个高效的片段组装算法,可以运行在一个廉价的计算平台。此外,在很多情况下,人们需要的是只有部分测序,或知道特定序列基因组中存在与否,不是整个基因组序列。
这个工作的主要动机是寻找一种有效的片段组装算法,可以运行在台式机上,然而,几乎可以找到正确的序列草案。
片段匹配该方法,形成叠连群,脚手架都嵌入在一个过程。此外如果研究者需要知道/确认只有特定的基因序列,其中的信息可以在序列重叠群池中(草案中定义部分3所示。4),她/他可能停止那一刻似乎叠连群池中,而不是继续更多的一代又一代的遗传搜索。
剩下的纸是组织如下。节2,鸟枪测序和问题的现有技术简要解释道。部分3致力于解释该算法。节4,我们国家实验设置和实际使用两个基因组序列的实验结果和讨论。结论是节5。
2。鸟枪测序方法
2.1。鸟枪测序
在本节中,我们解释基于Sanger测序片段组装。很长一段DNA序列解码需要克隆几册,把它分成碎片,阅读单独的片段,然后组装在正确的重建目标DNA序列。这个过程称为鸟枪测序,测序策略的基础。2000年迈尔斯等人成功测序果蝇果蝇基因组的长度使用全基因组鸟枪测序125 Mbps (wgs) [16),因此建立了wgs公认的技术。
wgs是用于测定草案于2001年人类基因组塞莱拉基因(26]。近年来,wgs还几个生物基因组解码,2005年由Mita黑猩猩(27),蜜蜂的蜜蜂2006年由魏因斯托克(28),和海胆Strongylocentrotus purpuratusSodergren等人于2006年(29日]。
我们的目标是相似的,创建基于wgs序列,使用GA做组装的部分。
2.2。wgs轮廓
wgs的整个过程分为两个步骤是克隆生物的一部分,破碎,和阅读。另一个是组装的计算部分片段。
2.2.1。生物部分
基本的猎枪过程始于一个复制份数的DNA序列切成不同长度的大量随机片段。太大或太小的片段会丢弃。剩余的碎片,那些用于组装,短的长度大约是2 kbp和长时间的大约10 kbp [11]。两端的碱基对的所有片段与DNA测序器读取,黑暗的部分片段,如图所示1。只有大约500年到1000年英国石油公司可以使用现在的音序器读技术。的基本序列两端的片段阅读音序器读,和一双读取从两端的片段mate-pairs。
从相当多的克隆,碎片的总碱基对读几次基地原基因的数量。通常,一个术语报道是用来衡量片段读取数据的冗余。它被定义为基础的总数从碎片读取源DNA的长度的比率(30.]: 在哪里片段的总数。基因组随机是支离破碎的。他们的读零件甚至不包括整个基因组如果报道很低。能够重建原来的基因组报道需要设置在8到10 (8 x10倍)。如果覆盖率高,覆盖原来的基因组的概率更高,部件组装的准确性提高。然而,片段的数量,因此计算复杂度也增加。即使报道10倍,部分原来的基因组片段可能不可用读取。
2.2.2。计算部分
原始的DNA序列,我们首先要确定重叠部分通过比较已经读过基础序列两端的片段,如图1。长基序列的长度没有差距,通过组装读取,被称为重叠群。图1显示两个重叠群是如何形成的。在这里,据推测,两个重叠的读取一个片段,一个一个前缀和后缀,来自同一地区的基因组。然而如此只有当重叠碱基对长度足够长,小序列基因组中重复出现。
两个读取双方的一个片段被称为mate-pair。位置和距离叠连群决心的伴侣对片段(图2)。因此,重叠群的子集与已知顺序组合在一起,这个过程称为脚手架。这是通过构建一个图的节点对应于叠连群,和一个有向边的连接两个节点当mate-pairs之间的桥梁。最近的汇编器包括一个单独的脚手架步骤。一个粗略的框架的原始基因组序列是由这个脚手架的过程。毕竟叠连群正确导向,命令,我们可以关闭两个重叠群之间的差距。这个过程称为缺口或完成。
Celera汇编[26)采用基于图论的脚手架算法使用成对交配。TIGR汇编[14雇佣了一个贪婪的启发式算法。
3所示。算法
我们提出了遗传算法技术是专门用于片段组装和类似的问题。这里的主要贡献是减少染色体步(信誉),这样可以减少GA与进步的一代染色体的长度。随着染色体长度减少,那么搜索空间和搜索越来越有效率。另一个贡献是染色体细化步骤(CRef),这是一个贪婪的突变提高解决方案的正确性由当地的基因重排。我们能够结合重叠的阶段(重叠群的形成)和脚手架的方式定义GA染色体的结构和信誉。细节在以下部分解释。
3.1。遗传算法的染色体的结构
基因遗传算法的染色体基因组片段,其中一个片段是一个基因。在遗传算法的染色体基因,有两个的信息读mate-pair序列,和未知长度之间的差距。这个片段结构不同于之前的工作,碱基对数组的片段。这使我们更现实的和复杂的问题。
鸟枪测序方法所产生的碎片在序列号标签,1,在那里,片段的总数。读取信息对应于不同的片段存储在片段数据表(FDT)。染色体是由这些组成的在随机片段测序。因此,染色体实际上是一个排列的数字1标签的不同的片段。许多这样的染色体,等于人口规模,创建。遗传算法的初始种群染色体的形成如图3。片段不是减少交叉等遗传操作的方式,因为边界的交叉和变异都是片段(基因的染色体)。因此,没有打破mate-pair被保留的信息。遗传搜索算法的流程如图4。不同的节块算法的解释如下3所示。2节3所示。5。
3.2。评价函数
搜索的目标是将更紧密的碎片来自同一地区的原始染色体。健身的GA染色体增加相邻基因匹配的碱基对数组。相似的相邻对GA染色体基因(实际上是基因组片段)找到健身计算如下: 染色体的基因已经屈指可数了来从左到右。在(2),和毗邻的片段,染色体是基因的总数。计算相似度(重叠),我们使用均为算法(31日],一对基因的检测校准动态规划。我们设定一个阈值重叠的判断是否存在一个真正的两个片段之间的匹配。如果两个片段和英国石油公司有相同的序列长度大于或等于,分数是1,否则为0。可能离散值0、1或2。因为每个片段都有两个读取如果两个,相似性是2读取两岸的碎片匹配。如果读取只有一边比赛,比分是1。如果我们将低,misassembling(错误)的概率增加。另一方面,如果我们设置高,匹配成功的概率很低的进展放缓遗传搜索。
3.3。选择、交叉和变异
3.3.1。选择
我们使用轮盘赌选择和精英保存。轮盘赌选择倾向于聚集在当地最大当几条染色体有更好的适应性。另一方面,正确的选择是更加公平照顾个人的健康。其他选择方法,比如排名和锦标赛选择,选择压力较少,因而早期收敛的概率较小。健身染色体之间的方差低我们的染色体设计,和由于信誉操作。(年底信誉操作每一个染色体健身再次重置低窄范围)。事实上,在一个预备实验证实roulette-selection是更高效的算法。
3.3.2。交叉和变异
我们不允许相同的多个副本GA染色体片段。以确保,我们使用订单交叉(牛)和交换,常用于解决TSP (32]。在牛,后代1直接拷贝基因父1,从一开始的交叉点。其余的基因复制父2保留的前后顺序父2,跳过已经复制的基因父1。后代2是建造类似。在这里,两点交叉也是可能的,但我们一点交叉使用。
突变是由简单的交换。两个基因在染色体随机选择和交换。在交换变异,也可以交换一个子集,所选择的基因子集。这样我们可以避免打破已经形成的子集。但是我们做了简单的一对基因交换。
3.4。减少染色体(信誉)的步骤
通过一代又一代染色体带个人片段长匹配碱基对通过评价函数和选择相邻的位置。一旦重叠的片段更近了,我们用信誉操作分开形成重叠群和重组基因在染色体的数组。这是在两个阶段完成,过滤阶段,结合阶段。这两个阶段一起被称为染色体还原步骤(信誉)。
在过滤阶段我们已经搜索重叠群形成于GA染色体。在精英染色体上执行搜索。如果重叠群超过某个阈值长度形成,所有片段包含在叠连群提取所有染色体。这缩短了染色体的长度。
进一步的细节如下。在这里,是阈值目标子串的长度,表示为碎片的数量。是生成的数字。是一个计数器计数。阈值的长度从其初始值减少,形成长字符串GA代发展越来越难做。是区间数代,它决定什么时候应该减少。
首先,初始化的值。和也初始化与每一代和增量。我们寻找/ s组成的子集最好的染色体片段,健身后评估。如果没有找到这样的子集,信誉不是开始和。这些子集/ s /首次发现,马克的片段中包含子集/ s。这些碎片从所有的染色体,删除和片段数据表(FDT)更新。与此同时,和。
标记片段结合基于重叠。叠连群/ s /存储在一个单独的数据库,我们称之为“叠连群池”在叠连群索引数据表(CDT)。这一阶段被称为结合阶段。如果其他重叠群/ s /已经叠连群池中,新成立的重叠群比较与叠连群/ s和结合这些尽可能长的重叠群。因此“叠连群池”和CDT更新。
如前所述,提取子集的长度,碎片数量而言,初始化。在每一代的子集的长度从最好的染色体片段提取。如果没有这样的子集是连续的组装代,因为当一个重叠群组成的碎片被发现,减少1。信誉的流算法显示为“是”决定钻石的一部分“子串形成了吗?”。
第一次当最初设置为最长的,数代的重叠群的形成也最长。我们设置作为一代又一代的数目,我们允许新子串的长度形成。只要我们找到长度的重叠群在代,不减少。如果,即使代,长度的子集不成立,我们降低我们的期望长度较小的子集。我们衰减参数,以及。一旦找到子字符串,过滤是通过哪些片段对应新组装的子串删除所有染色体。
后过滤阶段,结合阶段执行。当一个新的叠连群添加到叠连群池,我们试着把它与现有叠连群,如果可能的话,再重叠群。一旦形成,再叠连群进一步基因(基因片段)可以摆脱从染色体的方式是在过滤阶段完成的。
在过滤阶段的信誉,从染色体中提取子字符串的碎片,可能加入现有的重叠群的一端,或者它可能加入两个叠连群双方形成很长的重叠群。信息过滤操作是更新后的叠连群叠连群数据表(CDT)。他们之间的关系的信息,如果有的话,从获得的mate-pairs被添加到支架数据表(SDT)。因此,SDT拥有信息的标签重叠群和它们的相对位置。结合阶段开始,每次新叠连群相比现有重叠群和组合。CDT SDT后更新。使用简单的用户界面,重叠群的形成和支架可以可视化,可以由用户手动操作或专家,当可用。
随着叠连群变得更长,染色体短,遗传算法更有效地运行。每次结合阶段,用户可以检查可用的结果是否足够好(长时间)为她/他的目的。如果不是,遗传搜索仍在继续。
3.5。染色体细化(CRef)的步骤
而不是仅取决于遗传搜索,我们添加一个步骤来促进适当的排序更有效地通过手动贪婪的交换。这是一个简单和快速命名CRef启发式。
CRef提高解决方案的质量,通过重新安排在一个遗传算法的染色体片段的序列与目标基因的碱基序列相对应。当两个片段顺序A和B是定位在染色体由于高度重叠,重叠以下模式,如图5,是有可能的。
如果两个片段重叠模式4,很明显,他们在染色体序列顺序是错误的。我们交换这两个片段的位置。,在GA染色体片段的位置安排对应于他们的位置在原来的基因组,如图6。
这个概念可以延长范围扩大的片段比较,除此之外相邻片段。我们设定一个数值参数代表的范围比较碎片。例如,当,所有三个邻近片段进行了比较。不过,当评估一个遗传算法的染色体的适应性,我们只比较两个毗邻的片段,可以找到更高的相似性与一个片段一个或两个片段。这可能是探索通过设置一个值超过2和CRef运行。
CRef操作的详细说明如下。在这里,是一代又一代的数目,参数指定时间间隔,在一代又一代,CRef的周期性的执行。因此,如果是100,CRef将每100代执行。染色体是基因的总数。CRef操作需要大量计算能力,它运行在最好的几条染色体的人口。我们设定一个参数它指定数量的染色体CRef操作将会进行。
首先,我们设置的值,,。典型值是,,。每隔代,我们比较匹配的部分片段来,连续碎片,从最好的染色体。如果模式匹配(图4类型5)或片段的高相似性(但不是相邻)被发现,我们重新安排他们正确,如图6。
计算成本低因为CRef既不执行在所有染色体也在每一代执行。它仅限于几高适应性染色体(设定的参数)和周期性的规定执行。这两个参数设置取决于可用的计算能力和时间。
这两个步骤的信誉和CRef的结果我们的基因搜索的效率和质量大大提高。
4所示。实验和结果
在本节中,我们描述了我们的实验设置的细节,讨论的结果,并比较他们最常被称为遗传组装的帕森斯等人提出的。20.]。
4.1。实验基因组数据
我们使用了两个真正的基因组序列数据,也经常使用的其他研究人员,来测试我们的算法的有效性。他们在NCBI数据库中可用33]。重要的特性如表所示1。人类apolopoprotein POBF,长10089个基点。从LAMCG AMCG是初始40%的基地是噬菌体λ的完整基因组及其长度是20100个基点。我们按比例缩小的片段,片段长度读大小比实际鸟枪测序实验来减少计算时间。在实际实验中鸟枪测序,长度2 kbp的基因组片段10 kbp和读长度是800个基点1000个基点两岸的片段。我们克隆每个基因组序列和分裂成碎片的长度为200基点,至500基点模仿猎枪的方法,但同时降低10倍一个片段的长度。每一个读设置为50个基点,相应减少了12至20倍。因此这两个读和片段长度按比例缩小的类似因素相比,实际的猎枪片段组装(11]。我们也减少了覆盖从标准的价值8到10 x,这碎片的数量更少。这减少了计算负荷,但同时降低装配成功率的整个基因组。有进一步的解释部分4.2。
4.2。实验装置
我们实现了帕森斯的遗传算法相比,在相同实验条件下,算法与结果。我们之间的基本差异GA和帕森斯的GA如表所示2。
帕森斯描述的实验的论文,他们使用了一些POBF和AMCG数据。但是片段长度不同,整个片段是可读的。在我们的例子中,读只是小的长度(两头)上的记号是更接近于实际全基因组鸟枪测序方法显然更加困难。我们跑两帕森斯,我们的算法在相同的基因组数据。为了减少计算负荷,我们设置了报道4和5 x POBF和AMCG分别8 x相比更低的价值10 x用于实际的基因组测序。
4.3。遗传算法参数的设置
人口规模将在100染色体所生成的技术部分中解释3所示。1。交叉率和变异率为0.8和0.05,分别。与POBF序列在实验中,我们跑40个小时(约2000000的遗传操作2500000代),100小时(约50000006000000代)AMCG实验中,使用桌面PC (CPU是英特尔至强3.40 GHz和3.00 GB RAM)。阈值参数(部分3所示。2)设置为25个基点。长度的50%读是一个严格的设置。但是更短可能导致错误在最后组装阵列从毫无根据的匹配。事实上,在其他的实验中,5%的价值要低得多(读的是4050)通常是使用[26]。但是,如果我们设置在40到50,我们几乎不可能得到任何匹配,读长度为50。
我们定义节3所示。4。这个参数,引发信誉操作的开始,最初设定在一个值等于()。的价值步骤1中下降到吗。
在另一个预备实验,我们研究如何设置合适的参数值,用于CRef。我们尝试设置的值在2到5之间。重复的实验表明,给最好的结果。
4.4。结果
我们尝试20试验与不同的片段,和POBF AMCG基因组数据。在我们提出的技术,重叠群的数量和长度在“叠连群池”(检查部分3所示。4)。该算法重建率以及帕森斯的算法基础序列的比例在一段时间可以重建。我们清点的数量获得叠连群基地。这是好如果重建率高。然而即使重建率高,因此有许多缺口是不好的。重叠群的数量是衡量。重叠群的数量更少。如果频繁的差距,结果可能是无用的。错误的数量不匹配。不匹配意味着碎片组合不正确,也就是说,不是在原来的基因组。 This may happen when选择太短。使用我们的算法生成重叠群和帕森斯的GA, POBF和AMCG数据,比较表3。括号的次数100%的价值重建。
与我们的提议,我们可以重建的完整原始基因组POBF两次。尽管帕森斯的遗传算法可以获得完整的基因组在他们的论文中(20.),他们所使用的实验基因组数据没有任何差距,整个片段可读的使问题更复杂。与一个未读的差距在两个之间的片段读取片段数据,用于我们的实验是现实虽然重建原来的基因组序列是更加困难。
因为碎片是随机完成的,虽然整体覆盖4 x,基因组的某些部分可能只有一次的片段读取。帕森斯的算法,如果这些碎片不能匹配可以化合的重叠群的早期阶段,他们只剩下另一个子集已经形成。这是因为片段匹配只尝试了临近的碎片。这些片段是独处,只有突变可以组合它们。相反,我们建议的技术具有较高的那些片段相结合的机会。一个原因是,因为我们有两个读取分开的未读的部分,不太可能在两个碱基对读取在数量稀少。此外,由于信誉操作,有更多的整合碎片以及缩短整个染色体。他们一起改善结合唯一的机会读取。
使用POBF数据重叠群的平均长度在计划的GA略低于帕森斯的GA。然而,产生的支架我们提出的技术,如表所示4长。支架的长度显示只知道叠连群部分的长度。脚手架实现作为该算法的一部分,这是一个必要步骤鸟枪测序。
重建率的提高和执行时间数据所示7和8分别为POBF AMCG。我们检查了重建比每30分钟为AMCG POBF和每小时。
我们计算的重建比总长度的重叠群叠连群池。这是0%开始直到信誉开始其操作。因为我们设定一个阈值的子串长度从染色体取出,转移到叠连群池,定期改善重建比停滞不前。当经济停滞持续一段时间,信誉参数降低打破停滞。在每一个这样的时期,设置高希望得到长重叠群。当看起来如此长的重叠群不能建造,减少1。新发现叠连群GA染色体和重建率增加。我们可以清楚地观察到这种激增的曲线重建比率。对于POBF,有四个步骤。最初设置为5 (),后来减少到4 3和2。AMCG,有五个步骤,开始最后沦落到。
甚至在预定义的执行时间长度(40小时和100小时),结果是改善。通过增加和总执行时间的长度,能获得更好的结果。我们的算法能得到更好的结果与实际片段组装高覆盖率的数据,时间,读取和更低的价值(百分比读)。我们不能做这样的实验由于缺乏计算资源。
5。结论
我们提出了一种遗传算法的方法组装构建基因组序列的DNA片段。我们的染色体遗传算法不同于以前的方法。我们还添加了两个修改,减少染色体(信誉)和染色体步细化步骤(CRef),以提高遗传算法的效率优化片段组装。实际试验基因组数据,我们可以得到100%的POBF基因组序列。我们比较我们的算法与帕森斯的算法和显示该算法更好的结果。
我们使用的报道只有4 x而不是更实用10倍。更多的碎片覆盖相同的序列的一部分需要更好的重建率和准确性。同时,引入生物知识有助于有效片段组装和提高其准确性,,在未来,我们将与我们的遗传搜索链接,在信誉和CRef操作。在氨基酸和蛋白质的形成,有一些不同的规则排列的基地。使用这种模式的知识我们可以降低计算成本在相似性度量除了动态规划。我们计划包括领域知识来设计更高效的动态规划特定于这个问题。事实上,如果我们知道阈值的长度国会议员,高效得多比较块的核苷酸长度国会议员。我们的方法的另一个缺点。在染色体细化阶段,我们匹配程度的评估使用面向两个片段的遗传算法的染色体。事实上,取向可能会逆转,从他们出现在实际的基因组。比较这两个方向的相邻片段将计算更加复杂,但是我们可以实现整个基因组结构在GA代数量,以及更少数量的碎片。这两个修改我们的未来的工作。
虽然信誉步骤提出了分段装配问题,它适用于类似的问题像集群、路径搜索和其它组合优化。