基因組裝配中存在重復序列疊加時重疊群計數的推廣的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?。輊－rF／G。

但是，如圖1所示，當2個片段R1，R2為重復片段時，這2個重復片段將被所有的算法（soapdenovo算法也一樣）當成同一段序列的不同拷貝而被以高分組裝成一個片段，而他們之間原來的片段會因為blast分值較低被擠走，成為單獨的一個contig。這樣，由于repeat的存在會使得組裝之后的contig的個數與原來公式估計的不一樣了。依據文獻［3］中的結果，如果某個contig是2個repeat疊加的結果，則在長為r的序列中發現k－1個片段起點的概率為［（2r F／G）k／k?。輊－2rF／G。按這樣計算，如果這個contig是x個repeat片段疊加的結果，則這個概率應該是［（xrF／G）k／k?。輊－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