全局比對 Global Alignment

由芝加哥的Needleman和Wunsch兩位于上個世紀70年代初提出蝗蛙，常被稱之為Needleman-Wunsch算法。算法針對用戶指定的打分函數北发，確定性地找出兩條序列間的最優(yōu)比對。

Needle-Wunsch 算法對兩條序列所有殘基進行全局比對的局限性惊畏。

• 功能相關的蛋白之間雖然可能在整體序列上相差甚遠， 卻常常會具有相同的功能域
• 序列片段能夠獨立發(fā)揮特定的生物學功能，卻在不同蛋白之間相當保守
• 僅靠全局比對的算法無法發(fā)現這樣的片段
• 內含子的發(fā)現使得在做核酸水平的序列比對時必須要正確處理內含子導致的大片段的差異

局部比對 Local Alignment

1981年口猜，物理學家Temple Smith和數學家Michael Waterman在Journal of Molcular Biology上發(fā)表了一篇僅有四頁的文章淌实，提出Smith-Waterman局部比對算法

race back begins at the highest score inthe matrix and continues until you reach 0。And also the secondary best alignment

img

核心思想是給分數增加了下限0分

所有的回溯都是局部的老玛，所有的最終比對也是局部的麸粮。引入止損下限娇唯，差異擴大之后重啟比對梗摇，找到局部水平的相似性

空位罰分的改進

Affine gap penalty

• opening a gap receives a score ofd
• extending a gap receives a score of e
• Penalty = d + (n-1)* e

有限向量機

alt

擴展公式

alt

全局比對的時間復雜性

O(mn) 正比于m*n

全基因組比對

同源homology的分類

• 直系同源 ortholog 來自于不同的物種逢倍，演化過程中基因沒有丟失，各物種中都有

  chaining

• 旁系同源 paralog 來自于一個物種內部基因組的復制

  netting

NGS: Sequence alignment

Map the large numbers of short reads to a reference genome

• In a broader sense: Identify similar sequences (DNA, RNA, or protein) inconsequence of functional, structural, or evolutionary relationships between the them
• Applications: Genome assembly, SNP detection, homology search, etc

short: greater search sensitivity

large: faster search speed

In-exact alignment

BWA和bowtie的相關算法妆毕，大大減少了對服務器的要求

如何快速的知道某段序列大約在基因組的哪個位置

1. 如何定義大約這個概念

• Hamming Distance or Sequence Similarity
• Ungapped vs Gapped Global vs Local
• All positions or the single best

2. Efficiency depends on the data characteristics & goals

• Smith-Waterman: Exhaustive search for optimal alignments
• BLAST: Hash-table based homology searches
• Bowtie: BWT alignment for short read mapping

BWT算法

核心是繞最后一個序列轉圈

alt

• 先給每一個T做rotations,再進行sort,生成bw矩陣润努，最后一列從頭到尾就是BWT

• 回溯

  給每一個T的字母一個出現次數的排序,圖示如下

  alt

Suffix（后綴） Arrays

類似于電話本中的索引結構

What if we need to check many queries

• We don't need to check every page of the phone book to find 'Ma'

• Sorting alphabetically lets us immediately skip 96% (25/26) of the book withoutany loss in accuracy

Sorting the genome: Suffix Array (Manber & Myers1991)

• Sort every suffix of the genome

alt

所有具有相同prefix(前綴)的suffixes(后綴)會聚在一起，這樣就可以進行類似于二分法的排除

全基因組建立index

alt

• An array of integers giving the startingpositions of suffixes of a string inlexicographical order

• 從中間的index開始找扔罪，過濾一半

alt

效率

Total Runtime: O(m log n)

• More complicated, but much faster!
• Looking up a query loops 32 times instead of 3B

Searching the array is very fast, but it takes time to construct

• This time will be amortized over many, many searches
• Run it once "overnight" and save it away for all future queries
• 非常消耗內存

BLAST/Dot matrix

Indexing-based local alignment

alt

Basic Local Alignment Search Tool

圍繞最優(yōu)比對路徑進行計算

BLAST Ideas 核心思想: Seeding‐and‐extending

• Find matches (seed) between the query and subject 找到高度相似的小片段棘捣，種子

• Extend seed into High Scoring Segment Pairs (HSPs) 向兩端延伸并進行比對

  Run Smith‐Waterman algorithm on the specified region only

• Assess the reliability of the alignment 打分評估

將序列切分测砂，在數據庫中定位候選序列和位置

alt

得到候選序列和查詢序列的heatmap

去掉零散的hit,直留下對角線，形成hit cluster

以hit cluster為基礎向左右進行延伸直到分數不符合要去

在擴展的區(qū)域進行局部比對

alt

blast加速

• 標記低復雜度，易產生假陽性
• 考慮與種子相似的鄰居單字

分數評估，避免隨機因素

E value

alt

• n數據庫大小
• k和打分矩陣相關
• m長度
• s比對的分數

在隨機情況下獲得比當前分數高的可能比對條數，不是概率是個望值逊笆。p為0.05時子檀，E也是0.05亩进。

BLAST是一種啟發(fā)式算法，不確定有最優(yōu)解

alt

只在有效區(qū)域應用動態(tài)規(guī)劃算法

加入靠譜熊基地千元，和大家一起交流