基因组装配中存在重复序列叠加时重叠群计数的推广的Lander-Waterman定理

黄海云，张 屹

（1.河北科技大学图书馆，河北石家庄 050018；2.河北科技大学理学院，河北石家庄 050018）

基因组装配中存在重复序列叠加时重叠群计数的推广的Lander-Waterman定理

黄海云1，张 屹2

（1.河北科技大学图书馆，河北石家庄 050018；2.河北科技大学理学院，河北石家庄 050018）

针对基因组组装算法理论进行了改进，该研究对于经典的Lander-Waterman定理在repeat collapse存在的情况下进行了推广，对于判断基因组组装的contig的个数是否合理，组装质量是否可靠有重要的参考价值。

Lander-Waterman公式；重复序列；基因组组装；重叠群

第二代测序技术为人们提供了基因组测序的新思路。从数学上说，就是通过把基因组打成多重的小片段，然后用算法把它们组装在一起来得到全基因组序列。但是由于重复序列和杂合现象的存在，使得生成的de-Brujin图巨大复杂，难以压成一条序列［1－2］。更严重的是，重复序列会使contig的数量虚高，以至于无法估计真正的contig数量是多少［3－4］。

1 存在repeat叠加时重叠群个数的数学期望

基于2000年Science的刊文［3］中关于A-statistics的论述，笔者假设建立的某个生物的全基因组测序片段库中共有F个片段需要组装，基因组的大小已被事先用k-mer方法估计为G个AGCT字符。通过组装，得到若干个无法再通过重叠操作来加长的大片段，这些大片段叫做重叠群（contig）。设一个由k个片段组成的contig长为r个AGCT字符，即从这个contig的第一个组装片段的第一个字符到最后一个组装片段的最后一个字符之间的距离是r个字符。假设这个contig没有被重复取样（可按blast去冗余来保证这一点），则按照概率论的知识，在长为r的序列中发现k－1个片段起点的概率为［（r F／G）k／k！］e－rF／G。

但是，如图1所示，当2个片段R1，R2为重复片段时，这2个重复片段将被所有的算法（soapdenovo算法也一样）当成同一段序列的不同拷贝而被以高分组装成一个片段，而他们之间原来的片段会因为blast分值较低被挤走，成为单独的一个contig。这样，由于repeat的存在会使得组装之后的contig的个数与原来公式估计的不一样了。依据文献［3］中的结果，如果某个contig是2个repeat叠加的结果，则在长为r的序列中发现k－1个片段起点的概率为［（2r F／G）k／k！］e－2rF／G。按这样计算，如果这个contig是x个repeat片段叠加的结果，则这个概率应该是［（xrF／G）k／k！］e－xrF／G。同时，每次repeat的叠加都可以挤出一个contig［4］，则x个不可区分的重复片段将产生x－1个多余的contig。笔者所在研究组的飞蝗基因组的重复片段占整个基因组的1／2以上，repeat对于contig计数的影响是巨大的和不可忽视的。

图1 在组装时，重复片段R1与R2的叠加会引起contig个数的增加Fig.1 Repeat collapse of R1 and R2 increases a contig in assembly

2 Lander-Waterman的原定理

1988年，LANDER和WATERMAN给出了基因组组装时contig的分布定理［6］。他们假设2个片段之间至少要有全长的θ比例的片段重叠才能连接在一起，而且这个标准要足够严格以保证较小的假阳性出现。另外，假设基因组被打断后形成的片段集是完备的，覆盖整个基因组的。定理中所用的变量如下：

3 笔者推广的Lander-Waterman定理1

在Lander-Waterman定理［6］中有几个公式，其他的几个公式都可以据此推广到有重复片段叠加的一般情况，由于篇幅限制，本文只给出第一个公式的推广。

4 在基因组中的应用说明

基于给出的式（1）和式（2），可以计算出正确的contig的个数，可与实际组装生成的contig的个数相比较，来评价组装的质量以及受repeat叠加影响的严重程度。

［1］LI R，FAN W，TIAN G，et al.The sequence and de novo assembly of the giant panda genome［J］.Nature，2010，463：311-317.

［2］PEVZNER P A，TANG H，WATERMAN M S.An Eulerian path approach to DNA fragment assembly［J］.Proc Natl Acad Sci，2001，98：9 748-9 753.

［3］EUGENE W，MYER S.A whole-genome assembly of drosophila［J］.Science，2000，287：2 196.

［4］STEVEN L，SALZBERG J A.Beware of mis-assembled genomes［J］.Bioinformatics，2005，21：4 320-4 321.

［5］PAUL A P，HAIXU T，GLENN T.De novo repeat classification and fragment assembly［J］.Genome Research，2004，14：1 786-1 796.

［6］ERIC L，MICHAEL S W.Genomic mapping by fingerprinting random clones：A mathematical analysis［J］.Genomics，1988，2：231-239.

Generalized Lander-Waterman theorem under repeat collapse in genome assembly

HUANG Hai-yun1，ZHANG Yi2
（1.Library，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.College of Sciences，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China）

We improved the theory of algorithm of genome assembly which is a generalized Lander-waterman theorem under repeat collapse.It is important for appraising the rationality of the number of contig and the quality of genome assembly.

Lander-Waterman formula；repeat sequence；genome assembly；contig

O29 MSC（2010）主题分类号：60A10

A

1008-1542（2012）05-0384-02

2012-09-02；责任编辑：张士莹

国家自然科学基金资助项目（11171088）；河北省自然科学基金资助项目（A2011208002）

黄海云（1969-），女，内蒙古通辽人，馆员，主要从事生物信息学方面的研究。

张 屹副教授。E-mail：zhaqi1972＠163.com