推 aaeaiaoaua:太感謝學長了(跪拜) 11/05 14:39
※ 編輯: snark 來自: 156.111.130.203 (11/06 05:48)
※ 引述《aaeaiaoaua (蒲公英)》之銘言：
: 這裡有一篇博士論文，令人佩服地把分析NGS資料的過程介紹出來，
: 對我而言現在還是如讀天書，不過說不定板上有厲害的學長能看得懂。
: 有一個論壇叫做SEQanswer，充滿可怖的大大，他們都推薦這篇論文。
: http://seqanswers.com/
: 論文網址：
: http://ppt.cc/xshh
: 如果我研究出什麼(我好像也必須研究)
: 再跟大家分享。
這篇是對應我上次舉出的幾個問題
大家所想的方法之一
1.目前主流的NGS大多生成短序列 所以對於必須將所有序列的片段接起來
才可以得到正確的序列
假設是這樣的序列 ATCGATTCGATGC
正確將小片段駔合該這樣排alignment
ATCGAT
GATTCGA
TCGATGC
這是理想狀況 把序列依照彼此之間最大的相關性排起來就好了
但是有很多問題
2. 假設你有一個 read (讀出來的短序列) CGATGC
你會發現有兩個位置可能可以放
ATCGATTCGATGC
位置a CGATGC
位置b CGATGC
你怎麼知道哪個是對的?
這就是因為這一個小小的片段中就有兩個重複CGTA
如果給你參考序列 你可以知道A有一個配對不上 B每個都可以配對
所以應該是b比較正確
這就是有template的狀況之下去組合序列 會方便很多
3.但是如果這是火星生物 地球上的生物的序列都和他不像麻煩就大了
沒有 template時要組裝
稱為 de novo assembly
這時需要更多的數學統計技巧 來除錯 或知道哪裡裝錯了
4. 短序列組裝的另一個問題就是資料量極大
因為序列短而且彼此間關係位置不知道 所以同一個地方需要讀很多次
我們才能確定這是對的 還是有heterozygote 還是 讀錯 或者組裝錯誤
這些一樣有發展出不同的數學技巧來定義
簡單的閱讀
http://en.wikipedia.org/wiki/Shotgun_sequencing
Coverage
Hierarchical Shotgun sequencing
5. 資料極大 但是卻大多是重複的
ATCGAT
GATTCGA
TCGATGC
所以 開始有了 用表格來查詢的概念
我們不再秀這樣的表
1234567890ABC (座標)
ATCGAT
GATTCGA
TCGATGC
改用查的 1ATCGAT 7TCGATGC 假設是這樣 定義 每個片段不重複 只記錄起始點
你可以問我 第4-9是甚麼序列
我知道是 1的第四個元 開始 到結尾 接到 7的前三個
GAT+TCG
這樣就省了很多空間 但是序列的全貌要在查詢時計算
de Bruijn graphs 是利用graph theory其中的Directed Graph的一種
換言之這張圖有讀取的方向性
6.之後作者用圖形結構來找出序列甚麼時候可合併 甚麼時候應該是組裝錯誤
Figure 3.1: Schematic diagram of the three categories of errors in the Velvet
framework
想像成接龍就可以了
以上是錯誤結構 沒有尾 突出重複 還有交互連結(多重走法)
照道理說一條序列應該只有一個最佳最正確的順序
所以會看到文章中說
Figure 3.2: Schematic diagram of an iteration of the Tour Bus algorithm
The progression of the top path (through B0 and C0) is stopped because
D was previously visited.
D已經走過了 顯然有錯誤
Figure 3.3: Schematic diagram of the basic Tour Bus transformations
是校正錯誤結構的方法
要看懂這些文章建議先了解
1.NGS不同系統的原理
2.資料結構
3.演算法之dynamic programming
4. 離散數學 圖形理論
http://www.csie.ntnu.edu.tw/~u91029/Graph.html
5. 然後看看這個能不能看懂
google :
Velvet － de novo組裝的方法
6.當然還有很多其他解決方法
各有優點 各有缺點
Comparative Studies of de novo Assembly Tools for
Next-generation Sequencing Technologies
Bioinformatics (2011) doi: 10.1093/bioinformatics/btr319
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 156.111.130.135