最新版本請見：https://chenhsieh.com/post/bioinfo/12-kallisto/

放棄比對的話，新世界的大門就開啟囉

想知道手邊的兩條序列有多像，最直觀的方式就是把他們排在一起比一比。但是排列比對的概念與規則有很多人為的主觀假設，效能也沒有很好。下列五點是 Alignment-based 軟體的缺點：

第一點：alignment-based 的演算法基本上假設同源的序列，在線性排列上都會相對保守，也就是具有共線性 (collinearity)。但是其實這並不符合目前我們對於真實世界生物序列的了解，比如病毒基因體，其高突變率、遺傳重組率、基因橫向輸送與倍增機率，使整個基因體其實是一堆 lineage-specific 特異性序列的馬賽克拼貼。而這樣的現象也會發生在比較小的規模上，比如單一基因之蛋白質之功能區段也會有前後交換或倍增的現象。上述的不同規模之重組現象都使 alignment-based 適用性下降。

(人為假設與真實本質相反時該怎麼辦？截圖來自巨神兵現身東京)

第二點：alignment-based 演算法有其偵測極限。來個例子做好懂，兩條完全隨機的 20 個胺基酸序列，在允許 gap 的情況下，也可以達到 25% 的相似度；換作兩條完全隨機的 DNA/RNA 序列的話，相同條件的相似度甚至會高達 50%。也就是說，利用一般的 BLAST 來搜尋某序列的巨大基因家族之成員，當序列相似度來到 60-65% 的時候，其實無法判斷是長得很不一樣的同源序列抑或是完全不相干的序列，這個範圍被稱作模糊地帶 (twilight zone)。

(很多東西本來就分不大清楚～截圖來自吊帶襪天使)

第三點：alignment-based 演算法需要較大量的記憶體與計算資源，且隨著需要比對的序列長度增加，比對的可能組合也會暴增。即使有 dynamic programming 的幫助，不用遍歷所有可能解就能找到全域最佳解，其時間複雜度依然跟輸入序列之長度有關，因此套用到跨基因體之比較時依然不夠快。

(面對巨大之物時很多方法都會失效～截圖來自吊帶襪天使)

第四點：完全正確的多重序列比對 (multiple-sequence alignment) 其實是 NP-hard 的問題，這也就是為什麼近三十年來出現的演算法都是走 heuristics 流，而犧牲掉的準確性就有可能造成下游的分析如親緣比對出問題。

(為了速度就是必要犧牲一些準確性～截圖來自 REDLINE)

第五點：alignment-based 的演算法都有一些先驗 (priori) 的假設，比如：取代矩陣 (substitution matrices)、空一格要扣多少分 (gap penalties)、以及統計檢定之門檻，這些通通是人為主觀定義的。實際上許多人使用軟體的場景，就是將序列丟進去，輪流調整參數，直到跑出來的結果符合預期，這很難令人信服呈現的是最客觀最真實最自然的結果。

(軟體只會聽命行事，但是矛盾命令的本質或意義卻沒有人追究？截圖來自福音戰士新劇場版：Q)

綜上所述，將視線轉向 alignment-free 的演算法，屏棄了直觀的比對 (alignment) 過程，上述的各項問題也直接隨風飄散。大體而言，alignment-free 方法有兩大主流：基於次序列 (subsequences) 出現頻率的 word-based method、評估全長序列資訊內容的 information-theory based methods，兩大主流以外還有一些難以想像的存在，如：混沌遊戲 (chaos map)、迭代地圖 (iterated map)、改造自 word2vec 的 DNA2vec 向量表示法。

(遇見 alignment-free 開啟新世界～截圖來自吊帶襪天使)

黑科技般的 kallisto 堅持開頭不大寫

我的碩論中用到的轉錄體定量軟體就是 kallisto，還記得指導老師特別叫我去查軟體開頭該不該大寫～理解沒有錯的話，這次想要介紹的 kallisto 屬於 word-based method。第一次體會到這軟體 alignment-free 的神奇現場，是碩一時在中國參訪期間搭乘的客運上，埋頭用筆電遠端桌面連線使用在台灣的工作站電腦要取得基因表現量，指令打完，抬起頭看個風景，轉轉肩頸，本以為要等到回台灣才有結果，回過神來要闔上筆電的時候終端機竟然就顯示已經算完了！

(截圖來自 JoJo的奇妙冒險)

kallisto 官方網站美美，文件也寫得很清楚。

建立 index

實際定量

輸出結果包含一個 tsv 檔案，可以用 excel 直接開啟，包含下列欄位

kallisto 的開發者 Lior Pachter 最近又有神級新作，在手機上就能分析 single-cell RNA-seq，大家一起來膜拜吧～

如果有其他想了解的問題或是有誤的地方，請不吝指教或在下方留言～

參考資料與延伸閱讀

Modular and efficient pre-processing of single-cell RNA-seq

kallisto

Alignment-free sequence comparison: benefits, applications, and tools