[發(fā)明專利]雙向多步DeBruijn圖的錯(cuò)誤雙向邊識(shí)別與去除方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310672170.X
• 申請(qǐng)日: 2013-12-10
• 公開（公告）號(hào): CN103714263B
• 公開（公告）日: 2017-06-13
• 發(fā)明（設(shè)計(jì)）人: 孟金濤;張慧琳;彭豐斌;魏彥杰;馮圣中
• 申請(qǐng)（專利權(quán)）人: 深圳先進(jìn)技術(shù)研究院
• 主分類號(hào): G06F19/10
• 分類號(hào): G06F19/10
• 代理公司: 深圳市科進(jìn)知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙)44316
• 代理人: 沈祖鋒,郝明琴

技術(shù)領(lǐng)域

本發(fā)明涉及基因測(cè)序領(lǐng)域，具體涉及雙向多步De Bruijn圖的錯(cuò)誤雙向邊識(shí)別與去除方法。

背景技術(shù)

基因序列分析以算法與數(shù)學(xué)模型為核心，包括：基因數(shù)據(jù)的存儲(chǔ)與獲取、序列比對(duì)、測(cè)序與拼接、基因預(yù)測(cè)、生物進(jìn)化與系統(tǒng)發(fā)育分析、蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)、RNA結(jié)構(gòu)預(yù)測(cè)、分子設(shè)計(jì)與藥物設(shè)計(jì)、代謝網(wǎng)絡(luò)分析、基因芯片、DNA計(jì)算等。生物技術(shù)和計(jì)算機(jī)信息處理技術(shù)的緊密結(jié)合，加快了處理生物信息數(shù)據(jù)的速度，使得在盡短的時(shí)間內(nèi)對(duì)生物學(xué)做出準(zhǔn)確的詮釋，加快生物信息學(xué)的發(fā)展。

基因序列分析是對(duì)海量基因序列數(shù)據(jù)進(jìn)行分析，從而提取和挖據(jù)新的生物信息知識(shí)。涉及到計(jì)算機(jī)技術(shù)中的機(jī)器學(xué)習(xí)、模式識(shí)別、書籍分析與挖掘、組合數(shù)學(xué)、隨機(jī)模型、字符串、圖形算法、分布式計(jì)算、高性能計(jì)算、并行計(jì)算等。

基因是人類最基本的遺傳密碼，代表著每個(gè)人的生命信息?；蛐蛄猩洗嬖谥z傳位點(diǎn)的細(xì)微差異，這些遺傳密碼的多態(tài)性與人類的健康、致病機(jī)理、醫(yī)學(xué)治療有著相當(dāng)密切的關(guān)系。

自1977年Sanger測(cè)序技術(shù)問世以來，經(jīng)過三十多年的發(fā)展，DNA測(cè)序技術(shù)發(fā)展突飛猛進(jìn)，以高通量、短序列為特點(diǎn)的第二代測(cè)序技術(shù)逐漸占領(lǐng)市場(chǎng)，以單分子測(cè)序?yàn)樘攸c(diǎn)的第三代測(cè)序技術(shù)也逐漸出現(xiàn)，分別在測(cè)序特點(diǎn)上占有不同的優(yōu)勢(shì)。傳統(tǒng)的基因測(cè)序方法的數(shù)據(jù)提取和分析軟件經(jīng)過近10年來的研究與開發(fā)，目前已經(jīng)較為完善。但是，測(cè)序技術(shù)的發(fā)展，帶來了測(cè)序數(shù)據(jù)的變化，使得當(dāng)前存在的數(shù)據(jù)處理軟件不能滿足當(dāng)前生物醫(yī)學(xué)研究的需求。

新一代高通量測(cè)序方法在技術(shù)的應(yīng)用，可以在短時(shí)間內(nèi)完成整個(gè)基因組數(shù)據(jù)的測(cè)定。高通量測(cè)序方法的日新月異也同時(shí)對(duì)獲取的基因數(shù)據(jù)的分析處理方法提出了挑戰(zhàn)。目前，迫切需要開發(fā)能滿足高通量測(cè)序技術(shù)的海量數(shù)據(jù)處理的生物信息學(xué)平臺(tái)。面對(duì)個(gè)人基因組計(jì)劃及未來的個(gè)性化醫(yī)療前景，高效低成本的測(cè)序技術(shù)成為必然的趨勢(shì)。同時(shí)，簡(jiǎn)化高效的一站式完備的生物信息學(xué)數(shù)據(jù)分析平臺(tái)等完備的測(cè)序解決方案，也是極為重要不可或缺的發(fā)展方向。

然而新一代的高通量測(cè)序方法雖然測(cè)序通量高，但是卻會(huì)引入測(cè)序誤差，同時(shí)測(cè)序樣本本身由于基因突變，SNP，測(cè)序不均將在基因組組裝時(shí)構(gòu)造的雙向多步De Bruijn圖中引入錯(cuò)誤的頂點(diǎn)，以及錯(cuò)誤的雙向邊。而這些錯(cuò)誤的頂點(diǎn)以及錯(cuò)誤的雙向邊在對(duì)整個(gè)De Bruijn圖中容易引入分叉，而阻礙圖的收縮過程。

新一代的高通量測(cè)序方法產(chǎn)生的短基因片段的組裝導(dǎo)致大量的測(cè)序錯(cuò)誤，加大了組裝算法的計(jì)算量。大量的測(cè)序錯(cuò)誤，使得組裝錯(cuò)誤率增加，嚴(yán)重影響了組裝結(jié)果。

目前組裝算法策略分為兩類，一是基于Overlap-Layout-Consensus(OLC)的算法，另一個(gè)是基于DeBruijn圖的算法。其中，基于OLC組裝算法開發(fā)的軟件，如SSAKE、VCAKE、SHARCGS等，在基因長(zhǎng)序列組裝中更占有優(yōu)勢(shì)，但并不完全適用于新一代的短序列組裝。與OLC組裝算法不同，DeBruijn算法不再以read為單位組織數(shù)據(jù)，而是以k-mers為單位進(jìn)行數(shù)據(jù)組裝，其優(yōu)點(diǎn)主要有以下幾個(gè)方面：首先，以k-mers為單位進(jìn)行序列組裝，不影響節(jié)點(diǎn)的質(zhì)量，減少了冗余數(shù)據(jù)量；其次，在圖中重復(fù)區(qū)域只出現(xiàn)一次，便于識(shí)別，可以避免錯(cuò)誤的組裝，減小出錯(cuò)率；最后，采取將有重疊區(qū)域映射到同一條弧上的策略，從而簡(jiǎn)化了搜索路徑。目前，很多短序列組裝算法都使用這種框架，如Velvet、IDBA、SOAPdenovo，ABySS。

Velvet有效的利用De Bruijn圖，實(shí)現(xiàn)了高效的短序列組裝。Velvet以k-mer為基本單位構(gòu)建De Bruijn圖，利用圖的結(jié)構(gòu)，結(jié)合相應(yīng)的序列特征，簡(jiǎn)化圖的構(gòu)造，最終找到一條最優(yōu)路徑完成組裝過程。Velvet把焦點(diǎn)集中在錯(cuò)誤的數(shù)據(jù)產(chǎn)生的三種結(jié)構(gòu)上，即tip、bubble、以及erroneous connection。依照長(zhǎng)度原則和少數(shù)性原則，將長(zhǎng)度小于2k的均去除；利用Tour Bus算法中的深度優(yōu)先搜索策略合并bubble，最后利用覆蓋度閾值法去除了erroneous connection。該方法也充分利用了paired-end雙端信息，進(jìn)一步解決repeat問題，優(yōu)化了組裝效果。Velvet充分利用圖的結(jié)構(gòu)性質(zhì)，簡(jiǎn)化了數(shù)據(jù)冗余，速度較之前的算法有了很大的改進(jìn)。雖然它沒有在預(yù)處理階段對(duì)序列進(jìn)行糾錯(cuò)，但是其對(duì)錯(cuò)誤的預(yù)防機(jī)制，很大程度上的彌補(bǔ)了這方面的缺陷。這使得它更好的應(yīng)用在大型基因組序列的組裝中。