首先，小編先給大家介紹一些關(guān)于組裝的歷史。大家肯定也知道，這個(gè)組裝技術(shù)的發(fā)展是依賴于測序技術(shù)的。首先在一代測序的時(shí)候，測序數(shù)據(jù)量較少，成本較高，人們對于組裝的結(jié)首先，小編先給大家介紹一些關(guān)于組裝的歷史。大家肯定也知道，這個(gè)組裝技術(shù)的發(fā)展是依賴于測果預(yù)期也比較低，弄到contig水平就可以啦，還有就是這個(gè)組裝的物種基因組都偏小。因此那個(gè)時(shí)候的組裝軟件都是基于overlap的。然后呢，二代測序技術(shù)來了，數(shù)據(jù)量超高，成本也便宜啦。科研工作者就想啊，現(xiàn)在都二代了，這個(gè)組裝的預(yù)期得提高啊，得與時(shí)俱進(jìn)啊。但是基于overlap的組裝不了太長，而且超級慢，又加之，二代數(shù)據(jù)量太多，overlap扛不住啊。因此有人就開發(fā)出了基于圖論的組裝算法。然后呢，三代測序技術(shù)這兩年出來了，科學(xué)家一看，我x，這么長的read，那還搞毛圖論的算法，直接簡單粗暴點(diǎn)，用overlap多簡單，于是基于overlap的軟件又火了，去年一個(gè)三代基于圖論的軟件發(fā)表，將基于圖論的組裝再次放在了風(fēng)口浪尖。

大家好，我是生信人小編XIXI，與青壬同學(xué)遙相呼應(yīng)地，坐標(biāo)魔都西南……平時(shí)做項(xiàng)目總會遇到一些很有意思的文章或者算法，或者一些很有用的工具，會有拍案叫絕的沖動(當(dāng)然更多時(shí)候有想摔桌子的沖動)，所以呢希望能通過這個(gè)平臺和大家一起分享。

最近有在看一些關(guān)于從頭拼接(de novo)相關(guān)的文章。De novo的方法大部分是當(dāng)基因組、轉(zhuǎn)錄組或者蛋白組信息缺失嚴(yán)重或者想要研究修飾的時(shí)候使用，它可以不用借助任何參考組直接進(jìn)行推測拼接，但相對來說準(zhǔn)確度會比較低一些。

其實(shí)不難發(fā)現(xiàn)，大部分de novo的文章都是基于圖論分析，比如大部分基因組和轉(zhuǎn)錄組de novo；蛋白組的質(zhì)譜數(shù)據(jù)分析屬于“看圖說話”，以前的很多工具也是基于圖論，最近有出來很多基于機(jī)器學(xué)習(xí)的工具，運(yùn)行速度也有大幅提升，如果大家感興趣后邊也可以給大家講講。

最近想使用SOAPdenovo-Trans來進(jìn)行RNA-seq的de novo分析

所以對它的原理及運(yùn)行過程進(jìn)行了一下簡單摸索。在轉(zhuǎn)錄組方面，如果是測序比較完全的生物，大多數(shù)人是會選擇將測序的read直接匹配到參考基因組上邊的(還記得大明湖畔的Tophat和cufflinks么)；但是如果是一些參考基因組缺失的或者基因組非常龐大的物種，de novo的方法則可以很好地解決這個(gè)問題。

De Bruijn graph (DBG)可以說基本是大部分組裝方法的核心所在，有很大一部分的轉(zhuǎn)錄組拼接軟件(Oases，SOAPdenovo-Trans等)都是依賴于這個(gè)算法的。這里給大家做一個(gè)比較通俗的介紹。

比如我們手上有真實(shí)的RNA序列AUCGAAUCCCGAA，通過 RNA-seq可以得到的6條read：

那怎么從這6個(gè)小片段推導(dǎo)出它真實(shí)的序列信息呢？(如果你一眼看出來了，請?jiān)徫覍捜莸嘏帕姓R……)

首先，假如我們設(shè)定K-mers為3-mers，也就是說我們可以將所有的read都切割3個(gè)堿基長度的子序列，如下：

接著，我們可以將每個(gè)子序列都可以看成一個(gè)結(jié)點(diǎn)，每個(gè)read中的子序列結(jié)點(diǎn)可以依次用箭頭連接，依次建立這樣一張有向圖：

最后一張即為最終的de Bruijn graph (DBG)。那么怎么通過這張圖得到相應(yīng)的序列呢？

學(xué)過圖論的旁友們大概可以會心一笑，那就是解歐拉路徑(Eulerian Tour)！也就是在最后這張圖里使得每條路徑被經(jīng)過且僅經(jīng)過一次。這個(gè)例子里可以很簡單的可以看出來(真實(shí)的案例里大約看的出來算我輸……)：

串起來就可以得到：AUCGAAUCCCGAA，也就是我們最開始的RNA序列了！具體解歐拉途徑的算法圖論中應(yīng)該會有比較多的討論，有興趣的大神可以親手實(shí)現(xiàn)一下。

在該算法中K的選擇是有一定講究的，一般來說K小于等于最短read的長度，如果太短拼接效果又會比較差。SOAPdenovo-Trans中一般會設(shè)定~35作為K值。

De Bruijn graph的組裝方法相對時(shí)間復(fù)雜度比較低，為O(min(N,G))，G=genome length，N= total length of reads，與重疊方法的拼接過程相比可以大大節(jié)約時(shí)間成本；但它存在的問題是很可能你得到的路徑和你輸入的read是不匹配的，另外對于重復(fù)序列的處理也不是很棒。

更多套路，生信分析需求，請加微信：13895744602

歡迎關(guān)注生信人

TCGA | 小工具 | 數(shù)據(jù)庫 |組裝| 注釋 | 基因家族 | Pvalue

基因預(yù)測 |bestorf | sci | NAR | 在線工具 | 生存分析 | 熱圖

生信不死 | 初學(xué)者 | circRNA | 一箭畫心| 十二生肖 | circos

舞臺|基因組 | 黃金測序 | 套路 | 雜談組裝 | 進(jìn)化 | 測序簡史

總結(jié)

以上是生活随笔為你收集整理的图论解油瓶分油问题_一个很有趣的de novo图论算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。