早期動(dòng)態(tài)規(guī)劃算法
比較兩個(gè)序列的相似性（similarities）谭网。
編輯距離（edit distance）
加權(quán)編輯距離（weighted edit distance）和相似性評(píng)分（similarity score）
最優(yōu)全局比對(duì)（optimal global alignment）：Needleman-Wunsch算法
最優(yōu)局部比對(duì)（optimal local alignment）：Smith-Waterman算法
Gotoh’s算法：仿射空位罰分（affine gap penalties）
基本局部比對(duì)搜索工具BLAST（Basic Local Alignment Search Tool）
啟發(fā)式的（heuristic）序列比對(duì)方法嗜侮，遵循兩種思想：過(guò)濾和索引（filtration and indexing）拳球。
搜索和過(guò)濾绒极，種子和擴(kuò)展凑队。
過(guò)濾（filtration）：識(shí)別數(shù)據(jù)庫(kù)中與查詢片段（query）共享的小匹配模式（small matching patterns）的序列片段庇谆，稱為種子（seeds）缀台。數(shù)據(jù)庫(kù)的其余部分從考慮中丟棄棠赛。
擴(kuò)展：使用成本更高的算法（如動(dòng)態(tài)規(guī)劃）將種子擴(kuò)展為有意義的比對(duì)。
搜索：使用數(shù)據(jù)庫(kù)的預(yù)構(gòu)建索引（pre-built index）膛腐，通常是哈希表（hash table）睛约。
間隔種子（spaced seed），可以改善敏感性-特異性權(quán)衡（the sensitivity–specificity trade-off）哲身。
下一代測(cè)序和read mapping
讀段映射（read mapping）：在參考基因組序列（reference genomic sequence）中定位讀段（locating reads）并計(jì)算相應(yīng)的比對(duì)（alignments）辩涝。
比對(duì)軟件的效率來(lái)源：BWT-或FM-index索引結(jié)構(gòu)（indexing structure）。BWT-index可以被認(rèn)為是響應(yīng)二代測(cè)序數(shù)據(jù)量增加這一轉(zhuǎn)變的主要新的算法工具勘天。通用的（generic）類似BLAST的工具讓位給了專用的（dedicated）NGS讀段比對(duì)軟件怔揩。
與以BLAST為代表的基于哈希的索引基礎(chǔ)（hash-based indexes underpinning）支持種子和擴(kuò)展策略（seed-and-extend strategies）不同，BWT索引是一個(gè)全文索引（full-text index）脯丝。
宏基因組學(xué)（metagenomics）的無(wú)比對(duì)方法
宏基因組學(xué)將數(shù)百萬(wàn)reads比對(duì)到數(shù)千計(jì)的微生物基因組（microbial genomes）商膊。即使是專門的比對(duì)軟件也可能不滿足這項(xiàng)任務(wù)的實(shí)際時(shí)間要求。而且計(jì)算比對(duì)可能并不是必要的宠进，因?yàn)槲覀兺ǔＶ粚で笞R(shí)別給定read可能起源于的基因組晕拆。
放棄計(jì)算比對(duì)的想法，以較低的精度（lower accuracy）為代價(jià)材蹬，允許加速和內(nèi)存增益实幕。
無(wú)比對(duì)（alignment-free）或基于組合的比較（composition-based comparison）吝镣，將序列看作是出現(xiàn)在其中的一（多）組模式，例如固定長(zhǎng)度k的子字符串（substrings）（k-mers）昆庇。大多數(shù)用于全基因組測(cè)序數(shù)據(jù)的現(xiàn)代宏基因組分類器（classifiers）都是基于k-mer分析的末贾。
Bloom filters數(shù)據(jù)結(jié)構(gòu)。
Bloom filters已經(jīng)被應(yīng)用于表示de Bruijn graphs——一種廣泛用于基因組組裝的模型凰锡。
spaced k-mers
Sketch-based methods 基于素描/草圖的方法
tera-base規(guī)模的數(shù)據(jù)分析方法：局部敏感散列（locality-sensitive hashing未舟，LSH）圈暗，思想是將復(fù)雜的對(duì)象（例如長(zhǎng)序列）映射（map）到較小的對(duì)象掂为，稱為草圖或指紋（sketches or fingerprints），這樣相似的對(duì)象很可能被映射到相似或相同的草圖员串。這允許使用草圖上的相應(yīng)操作代替對(duì)輸入對(duì)象的操作（搜索勇哗、比較、序列重疊等）寸齐。
LSH的一個(gè)具體實(shí)例欲诺，稱為MinHash，早些時(shí)候被應(yīng)用于尋找類似的網(wǎng)絡(luò)文檔渺鹦。MinHash可以看作是遵循無(wú)比對(duì)模式扰法，認(rèn)為序列是它們的k-mers的集合，通過(guò)比較在一個(gè)或幾個(gè)散列函數(shù)（hash functions）下使用相應(yīng)的k-mers的最小哈希值（minimum hash values）定義的集合的草圖來(lái)估計(jì)Jaccard index毅厚。
通過(guò)使用minimizers作為種子來(lái)改進(jìn)基于種子的序列搜索（seed-based sequence search (cf above)）的方法塞颁。對(duì)于map由“第三代測(cè)序技術(shù)”（third-generation sequencing technologies）產(chǎn)生的長(zhǎng)reads特別有用。
From genomics to population genomics從基因組學(xué)到群體基因組學(xué)
? ? 多基因組基因分型（genotyping multiple genomes）并不局限于個(gè)體間（inter-individual）遺傳變異的研究吸耿，而是包括一個(gè)細(xì)胞群體中的個(gè)體內(nèi)部異質(zhì)性（intra-individual heterogeneity）祠锣。
在大規(guī)模測(cè)序的支持下，基因組學(xué)現(xiàn)在進(jìn)入了一個(gè)新的階段咽安，其特征是潛在的方法范例（methodological paradigm）的另一次轉(zhuǎn)變：現(xiàn)在基因組學(xué)的基本對(duì)象從一個(gè)物種的“參考基因組”（reference genome）轉(zhuǎn)變?yōu)橐粋€(gè)個(gè)體或細(xì)胞群體的集體基因組（collective genome）伴网，有時(shí)被稱為泛基因組（pan-genome）。
從計(jì)算的角度來(lái)看妆棒，群體基因組學(xué)（population genomics）的主要問(wèn)題是如何代表（how to represent）群體的集體基因組（a collective genome of a population）澡腾，以允許更有效的算法處理，另一方面糕珊，捕捉單個(gè)基因組的變化动分。一種方法，將共同的基因組片段（common genomic fragments）表示在一個(gè)副本（single copy）中放接，從而將一個(gè)單一的參考基因組序列替換為一個(gè)標(biāo)記的圖（a labeled graph）刺啦，其路徑（paths）代表單個(gè)基因組。
壓縮基因組學(xué)（Compressive genomics）是一種試圖從基因組數(shù)據(jù)的全局“拓?fù)洹苯Y(jié)構(gòu)（global ‘topological’ structure）中獲益的范例纠脾。
補(bǔ)充內(nèi)容：
索引（index）
人類基因組單倍體有30億堿基玛瘸，二代測(cè)序目前的長(zhǎng)度通常為150蜕青，在基因組中找到序列片段位置，類似于找到一本書在圖書館書架的位置糊渊，如果從頭開始一本一本找十分耗費(fèi)時(shí)間右核，但從圖書館的書架索引找到對(duì)應(yīng)的位置就會(huì)方便很多。從索引中找的關(guān)鍵是渺绒，這索引要長(zhǎng)什么樣才能滿足快速找到的目的贺喝。
有各種各樣建立索引的途徑（indexing）。如把基因組拆成無(wú)數(shù)小段建立索引（substring法）宗兼、把基因組做成樹結(jié)構(gòu)（suffix trie或者tree）躏鱼、做成數(shù)組（suffix array）、做BWT轉(zhuǎn)化（FM-index）殷绍。其實(shí)目的只有一個(gè)染苛，能快速找到測(cè)序序列在基因組的位置。這些方法各有優(yōu)缺點(diǎn)主到，需要根據(jù)情況選擇最合適的方法茶行。選擇BWT并不是因?yàn)樗羁欤蔷C合效果最好（最快的檢索方法是數(shù)組法登钥，但缺點(diǎn)是會(huì)制造一個(gè)巨大的基因組索引畔师，而且速度也不是本質(zhì)性的提升）。
后綴樹
后綴就是包含最后一個(gè)字符的子序列牧牢。最后一個(gè)字符后面還要加上一個(gè)$看锉，表示結(jié)尾。
后綴i = Si, Si+1, …, Sn结执。
功能1：查找字符串s是否在字符串S中
方法：從樹根開始度陆，與s的字符逐一比對(duì)。
功能2：查找字符串s在字符串S中的重復(fù)次數(shù)
方法：從樹根開始献幔，按照功能1的方法找到s懂傀，然后看s之后有幾片樹葉，則重復(fù)幾次蜡感。
功能3：找字符串S中的最長(zhǎng)重復(fù)子序列
方法：找到從樹根到所有節(jié)點(diǎn)（非葉片）的子字符串蹬蚁，從中找到最長(zhǎng)的。
$的作用：如果某一個(gè)后綴是另一個(gè)后綴的前綴郑兴，那么需要用$標(biāo)識(shí)出一個(gè)獨(dú)立的葉片犀斋。
Trie數(shù)據(jù)結(jié)構(gòu)
Trie (the term comes from retrieval檢索) is a data structure that stores all of the suffixes后綴/prefixes前綴 of a string.
Trie樹，又稱字典樹情连，單詞查找樹或者前綴樹叽粹，是一種用于快速檢索的多叉樹結(jié)構(gòu)，如英文字母的字典樹是一個(gè)26叉樹，數(shù)字的字典樹是一個(gè)10叉樹虫几。Trie一詞來(lái)自retrieve锤灿，發(fā)音為/tri:/ “tree”，也有人讀為/tra?/ “try”辆脸。Trie樹可以利用字符串的公共前綴來(lái)節(jié)約存儲(chǔ)空間但校。
Trie的核心思想是空間換時(shí)間：利用字符串的公共前綴來(lái)降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。
典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串）啡氢，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)状囱。它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希表高倘是。
