[發明專利]一種基于簇圖結構的并行基因拼接方法

有效

• 申請號: 201310666751.2
• 申請日: 2013-12-09
• 公開（公告）號: CN103761453B
• 公開（公告）日: 2017-10-27
• 發明（設計）人: 陳科;徐魁
• 申請（專利權）人: 天津工業大學
• 主分類號: G06F19/18
• 分類號: G06F19/18
• 代理公司: 天津市杰盈專利代理有限公司12207
• 代理人: 朱紅星

1.一種基于簇圖結構的并行基因拼接方法，其特征在于所述基因拼接方法包含創建簇圖和搭建并行框架；

其中創建簇圖指的是：根據原始基因數據與Velvet、ABySS、SOAPdenovo、Ray這些算法

生成結果長序列之間的映射結果對scaffold進行相似性和匹配度計算，然后進行聚簇，簇中的兩個匹配的scaffold構成scaffold對，所有scaffold對中具有多個匹配的區域，以這些區域作為節點，它們之間的連接構成邊，創建簇圖；搭建并行框架指的是：貫穿在整個基因拼接方法的各個步驟中，包括讀寫文件、構建索引、短讀長映射、scaffold聚簇、構建簇圖、搜索路徑步驟；采用的并行框架對每個步驟中的任務進行分割、執行、合并，執行過程中節省了大量的時間，包括以下步驟：

（1）數據準備：準備所有的輸入數據，包括兩種數據，一是原始的雙端讀長數據，這個在NCBI上獲得；二是Velvet、ABySS、SOAPdenovo、Ray這些算法的結果數據scaffold；這兩類數據分別要進行預處理；

（2）構建索引： 構建索引就是要將結果數據scaffold所包含的序列建立一個索引結構，這個索引結構為下一步讀長映射提供基礎；索引構建完畢，將得到每個算法的scaffold的索引文件；

（3）讀長映射：利用索引將read-pair映射到scaffold上，首先將上一步中生成的索引文件讀入到內存，接下來就是對讀長進行映射了，映射的方式并沒有采用讀長序列中所有的堿基，而是只使用了讀長對的內側的一部分，L=3*k-mer，所謂內側是指left read的右端和right read的左端；規定只有這部分映射成功之后，整個讀長對就可映射成功，映射結果表現為一個scaffold的不同的位置上有多個read與之映射；

（4）scaffold聚簇：為了下一步進行拼接生成簇圖，首先對所有的scaffold進行聚簇；每個scaffold的特征由上一步映射結果得到的read的集合來體現，根據計算不同scaffold對應的read集合之間的相關性和scaffold之間的匹配程度，找到互補的、潛在的、可拼接的scaffold對，并將它們聚到同一個簇中，對于每一個簇將會通過構建簇圖并尋找最長路徑的方式得到長序列；

（5）構建簇圖：構建簇圖的過程包括生成子圖和合并子圖兩個步驟，即對于簇中第個contig生成子圖，然后將簇中所有合并成能表示一個簇的最終圖，最后求解簇圖的最長路徑；最長路徑所包含的堿基序列即為方法拼接之后的結果；

（6）生成拼接結果：得到簇圖之后，通過計算簇圖的最長路徑，根據路徑信息得到拼接成的基因序列。

2.根據權利要求1所述的基于簇圖結構的并行基因拼接方法，其特征在于數據準備步驟要下載的基因序列原始數據要求是來自Illumina測序平臺生成的雙端短序列，文件格式要是fasta或fastq格式，其它格式的文件需要先進行轉換；對于從NCBI官方網站上下載的數據一般是SRA格式，需要使用SRA Toolkit工具包將下載得到的*.sra文件轉化成要求的fastq和fasta格式的數據文件；

運行命令：

轉換得到兩個文件，是讀長對分別存儲的左讀長和右讀長的fastq文件；

數據準備步驟要準備的第二類數據是長序列scaffold文件；該scaffold文件是其他基因拼接算法的結果文件，所以需要配置并運行這些算法，并得到最終結果，這些拼接算法是Velvet、ABySS、SOAPdenovo、Ray。

3.根據權利要求1所述的基于簇圖結構的并行基因拼接方法，其特征在于，所述索引結構是首先共享的索引可供多個線程訪問，其次索引結構采用的是預分配空間直接存取的方式，這種方式節省了映射過程中查找序列的時間。

4.根據權利要求1所述的基于簇圖結構的并行基因拼接方法，其特征在于作為方法輸入數據的DNA序列是經過隨機打斷生成的碎片序列，基因序列的無模板拼接就是要將這些碎片序列拼接成更長的序列；高通量測序中read一般會成對出現，也就是以read-pair形式存在。