smithwaterman演算法得分

『壹』 生物信息學習題，如何回答~

建議你找本書看看，這都是基本的東西

『貳』 生物信息學有哪些經典的應用實例

1,測序與序列比對(Sequence Alignment)
測序是生物信息學的基礎和主要數據來源，可以是人類數據也可以是其他的數據。序列比對的基本問題是比較兩個或兩個以上符號序列的相似性或不相似性.從生物學的初衷來看,這一問題包含了以下幾個意義:從相互重疊的序列片斷中重構DNA的完整序列.在各種試驗條件下從探測數據(probe data)中決定物理和基因圖存貯,遍歷和比較資料庫中的DNA序列比較兩個或多個序列的相似性在資料庫中搜索相關序列和子序列尋找核苷酸(nucleotides)的連續產生模式找出蛋白質和DNA序列中的信息成分序列比對考慮了DNA序列的生物學特性,如序列局部發生的插入,刪除(前兩種簡稱為indel)和替代,序列的目標函數獲得序列之間突變集最小距離加權和或最大相似性和,對齊的方法包括全局對齊,局部對齊,代溝懲罰等.兩個序列比對常採用動態規劃演算法,這種演算法在序列長度較小時適用,然而對於海量基因序列(如人的DNA序列高達109bp),這一方法就不太適用,甚至採用演算法復雜性為線性的也難以奏效.因此,啟發式方法的引入勢在必然,著名的BALST和FASTA演算法及相應的改進方法均是從此前提出發的.
2, 蛋白質結構比對和預測
基本問題是比較兩個或兩個以上蛋白質分子空間結構的相似性或不相似性.蛋白質的結構與功能是密切相關的,一般認為,具有相似功能的蛋白質結構一般相似.蛋白質是由氨基酸組成的長鏈,長度從50到1000~3000AA(Amino Acids),蛋白質具有多種功能,如酶,物質的存貯和運輸,信號傳遞,抗體等等.氨基酸的序列內在的決定了蛋白質的3維結構.一般認為,蛋白質有四級不同的結構.研究蛋白質結構和預測的理由是:醫葯上可以理解生物的功能,尋找dockingdrugs的目標,農業上獲得更好的農作物的基因工程,工業上有利用酶的合成.直接對蛋白質結構進行比對的原因是由於蛋白質的3維結構比其一級結構在進化中更穩定的保留,同時也包含了較AA序列更多的信息.蛋白質3維結構研究的前提假設是內在的氨基酸序列與3維結構一一對應(不一定全真),物理上可用最小能量來解釋.從觀察和總結已知結構的蛋白質結構規律出發來預測未知蛋白質的結構.同源建模(homology modeling)和指認(Threading)方法屬於這一范疇.同源建模用於尋找具有高度相似性的蛋白質結構(超過30%氨基酸相同),後者則用於比較進化族中不同的蛋白質結構.然而,蛋白結構預測研究現狀還遠遠不能滿足實際需要.
3, 基因識別,非編碼區分析研究.
基因識別的基本問題是給定基因組序列後,正確識別基因的范圍和在基因組序列中的精確位置.非編碼區由內含子組成(introns),一般在形成蛋白質後被丟棄,但從實驗中,如果去除非編碼區,又不能完成基因的復制.顯然,DNA序列作為一種遺傳語言,既包含在編碼區,又隱含在非編碼序列中.分析非編碼區DNA序列目前沒有一般性的指導方法.在人類基因組中,並非所有的序列均被編碼,即是某種蛋白質的模板,已完成編碼部分僅占人類基因總序列的3~5%,顯然,手工的搜索如此大的基因序列是難以想像的.偵測密碼區的方法包括測量密碼區密碼子(codon)的頻率,一階和二階馬爾可夫鏈,ORF(Open Reading Frames),啟動子(promoter)識別,HMM(Hidden Markov Model)和GENSCAN,Splice Alignment等等.

『叄』 smith waterman演算法中的動態規劃中怎麼將所有的路徑顯示出來

function fib(n)
var previousFib := 0, currentFib := 1
if n = 0
return 0
else if n = 1
return 1
repeat n-1 times
var newFib := previousFib + currentFib
previousFib := currentFib
currentFib := newFib
return currentFib
在這兩個例子，我們都只計算fib(2)一次，然後用它來計算fib(3)和fib(4)，而不是每次都重新計算。

2. 一種平衡的0-1矩陣
考慮n*n矩陣的賦值問題：只能賦0和1，n為偶數，使每一行和列均含n/2個0及n/2個1。例如，當n=4時，兩種可能的方案是：
+ - - - - + + - - - - +
| 0 1 0 1 | | 0 0 1 1 |
| 1 0 1 0 | | 0 0 1 1 |
| 0 1 0 1 | | 1 1 0 0 |
| 1 0 1 0 | | 1 1 0 0 |
+ - - - - + + - - - - +
問：對於給定n，共有多少種不同的賦值方案。
至少有三種可能的演算法來解決這一問題：窮舉法（brute force）、回溯法（backtracking）及動態規劃（dynamic programming）。窮舉法列舉所有賦值方案，並逐一找出滿足平衡條件的方案。由於共有C(n, n/2)^n種方案（在一行中，含n/2個0及n/2個1的組合數為C(n,n/2)，相當於從n個位置中選取n/2個位置置0，剩下的自然是1），當n=6時，窮舉法就已經幾乎不可行了。回溯法先將矩陣中部分元素置為0或1，然後檢查每一行和列中未被賦值的元素並賦值，使其滿足每一行和列中0和1的數量均為n/2。回溯法比窮舉法更加巧妙一些，但仍需遍歷所有解才能確定解的數目，可以看到，當n=8時，該題解的數目已經高達116963796250。動態規劃則無需遍歷所有解便可確定解的數目（意思是劃分子問題後，可有效避免若乾子問題的重復計算）。
通過動態規劃求解該問題出乎意料的簡單。考慮每一行恰含n/2個0和n/2個1的k*n(1<=k<=n)的子矩陣，函數f根據每一行的可能的賦值映射為一個向量，每個向量由n個整數對構成。向量每一列對應的一個整數對中的兩個整數分別表示該列上該行以下已經放置的0和1的數量。該問題即轉化為尋找f((n/2,n/2),(n/2,n/2),...,(n/2,n/2))（具有n個參數或者說是一個含n個元素的向量）的值。其子問題的構造過程如下：
1) 最上面一行（第k行）具有C(n, n/2)種賦值；
2) 根據最上面一行中每一列的賦值情況（為0或1），將其對應整數對中相應的元素值減1；
3) 如果任一整數對中的任一元素為負，則該賦值非法，不能成為正確解；
4) 否則，完成對k*n的子矩陣中最上面一行的賦值，取k=k-1，計算剩餘的(k-1)*n的子矩陣的賦值；
5) 基本情況是一個1*n的細小的子問題，此時，該子問題的解的數量為0或1，取決於其向量是否是n/2個(0, 1)和n/2個(1, 0)的排列。
例如，在上面給出的兩種方案中，向量序列為：
((2, 2) (2, 2) (2, 2) (2, 2)) ((2, 2) (2, 2) (2, 2) (2, 2)) k = 4
0 1 0 1 0 0 1 1
((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k = 3
1 0 1 0 0 0 1 1
((1, 1) (1, 1) (1, 1) (1, 1)) ((0, 2) (0, 2) (2, 0) (2, 0)) k = 2
0 1 0 1 1 1 0 0
((0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1, 0) (1, 0)) k = 1
1 0 1 0 1 1 0 0
((0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0, 0), (0, 0) (0, 0))
動態規劃在此的意義在於避免了相同f的重復計算，更進一步的，上面著色的兩個f，雖然對應向量不同，但f的值是相同的，想想為什麼吧:D。
該問題解的數量（序列a058527在OEIS）是1, 2, 90, 297200, 116963796250, 6736218287430460752, ...
下面的外部鏈接中包含回溯法的Perl源代碼實現，以及動態規劃法的MAPLE和C語言的實現。

3. 棋盤
考慮n*n的棋盤及成本函數C(i,j)，該函數返回方格(i,j)相關的成本。以5*5的棋盤為例：
5 | 6 7 4 7 8
4 | 7 6 1 1 4
3 | 3 5 7 8 2
2 | 2 6 7 0 2
1 | 7 3 5 6 1
- + - - - - -
| 1 2 3 4 5
可以看到：C(1,3)=5
從棋盤的任一方格的第一階（即行）開始，尋找到達最後一階的最短路徑（使所有經過的方格的成本之和最小），假定只允許向左對角、右對角或垂直移動一格。
5 |
4 |
3 |
2 | x x x
1 | o
- + - - - - -
| 1 2 3 4 5
該問題展示了最優子結構。即整個問題的全局解依賴於子問題的解。定義函數q(i,j)，令：q(i,j)表示到達方格(i,j)的最低成本。
如果我們可以求出第n階所有方格的q(i,j)值，取其最小值並逆向該路徑即可得到最短路徑。
記q(i,j)為方格(i,j)至其下三個方格（(i-1,j-1)、(i-1,j)、(i-1,j+1)）最低成本與c(i,j)之和，例如：
5 |
4 | A
3 | B C D
2 |
1 |
- + - - - - -
| 1 2 3 4 5
q(A) = min(q(B),q(C),q(D)) + c(A)
定義q(i,j)的一般形式：
|- inf. j<1 or j>n
q(i,j) = -+- c(i,j) i=1
|- min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j) otherwise.
方程的第一行是為了保證遞歸可以退出（處理邊界時只需調用一次遞歸函數）。第二行是第一階的取值，作為計算的起點。第三行的遞歸是演算法的重要組成部分，與例子A、B、C、D類似。從該定義我們可以直接給出計算q(i,j)的簡單的遞歸代碼。在下面的偽代碼中，n表示棋盤的維數，C(i,j)是成本函數，min()返回一組數的最小值：
function minCost(i, j)
if j < 1 or j > n
return infinity
else if i = 1
return c(i,j)
else
return min(minCost(i-1,j-1),minCost(i-1,j),minCost(i-1,j+1))+c(i,j)
需要指出的是，minCost只計算路徑成本，並不是最終的實際路徑，二者相去不遠。與Fibonacci數相似，由於花費大量時間重復計算相同的最短路徑，這一方式慢的恐怖。不過，如果採用自下而上法，使用二維數組q[i,j]代替函數minCost，將使計算過程快得多。我們為什麼要這樣做呢？選擇保存值顯然比使用函數重復計算相同路徑要簡單的多。
我們還需要知道實際路徑。路徑問題，我們可以通過另一個前任數組p[i,j]解決。這個數組用於描述路徑，代碼如下：
function computeShortestPathArrays()
for x from 1 to n
q[1, x] := c(1, x)
for y from 1 to n
q[y, 0] := infinity
q[y, n + 1] := infinity
for y from 2 to n
for x from 1 to n
m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
q[y, x] := m + c(y, x)
if m = q[y-1, x-1]
p[y, x] := -1
else if m = q[y-1, x]
p[y, x] := 0
else
p[y, x] := 1
剩下的求最小值和輸出就比較簡單了：
function computeShortestPath()
computeShortestPathArrays()
minIndex := 1
min := q[n, 1]
for i from 2 to n
if q[n, i] < min
minIndex := i
min := q[n, i]
printPath(n, minIndex)
function printPath(y, x)
print(x)
print("<-")
if y = 2
print(x + p[y, x])
else
printPath(y-1, x + p[y, x])

『肆』 序列比對的分類

把兩個以上字元序列對齊，逐列比較其字元的異同，使得每一列字元盡可能一致，以發現其共同的結構特徵的方法稱為多序列比對 。多序列比對問題其實是雙序列比對問題的推廣。
多序列比對的目標是使得參與比對的序列中有盡可能多的列具有相同的字元，即，使得相同殘基的位點位於同一列，這樣以便於發現不同的序列之間的相似部分，從而推斷它們在結構和功能上的相似關系，主要用於分子進化關系，預測蛋白質的二級結構和三級結構、估計蛋白質折疊類型的總數，基因組序列分析等。
由於多序列比對能夠揭示雙序列比對所不能發現的序列微弱相似性、序列模式和功能位點，因而對蛋白質和核酸序列的結構、功能和進化研究更加有用。 1981年，由F. Smith 和 M.Waterman首次提出局部比對演算法，動態規劃方法通過較少的改動便可以用來識別匹配的子序列， 並且忽略匹配區域之前或之後的失配和空位;局部比對時，表中小於零的位置用零代替。主要用來考察兩序列的某些特殊片段。

『伍』 在WGS檢驗程序,列出至少五個在抽箱過程中應遵循的關鍵點是什麼

人類基因組中的變異和人類的演化、疾病風險等方面都有著密切的聯系。當前二代短讀長高通量測序技術（NGS），雖然能夠讓測序成本大大降低，但這種短讀長的測序方法也給基因組的變異檢測（特別是結構性變異檢測）帶來了不小的挑戰。SNP和Indel大家應該都見得比較多了，因此在這篇文章里我將主要討論常見結構性變異的檢測方法和有關軟體以及它們的一些優缺點。

變異的分類

在開始之前，有必要先梳理一下人類基因組上的變異種類，按照目前業界的看法可以分為如下三個大類：

• 單鹼基變異，即單核苷酸多態性(SNP)，最常見也最簡單的一種基因組變異形式；

• 很短的Insertion 和 Deletion，也常被我們合並起來稱為Indel。主要指在基因組某個位置上發生較短長度的線性片段插入或者刪除的現象。強調線性的原因是，這里的插入和刪除是有前後順序的與下述的結構性變異不同。Indel長度通常在50bp以下，更多時候甚至是不超過10bp，這個長度范圍內的序列變化可以通過Smith-Waterman 的局部比對演算法來准確獲得，並且也能夠在目前短讀長的測序數據中較好地檢測出來；

• 基因組結構性變異（Structure Variantions，簡稱SVs），這篇文章的重點，通常就是指基因組上大長度的序列變化和位置關系變化。類型很多，包括長度在50bp以上的長片段序列插入或者刪除（Big Indel）、串聯重復（Tandem repeate）、染色體倒位（Inversion）、染色體內部或染色體之間的序列易位（Translocation）、拷貝數變異（CNV）以及形式更為復雜的嵌合性變異。

• 值得一提的是，研究人員對基因組的結構性變異發生興趣，主要還是由於在研究中發現：

• SVs對基因組的影響比起SNP更大，一旦發生往往會給生命體帶來重大影響，比如導致出生缺陷、癌症等；

• 有研究發現，基因組上的SVs比起SNP而言，更能代表人類群體的多樣性特徵；

• 稀有且相同的一些結構性變異往往和疾病（包括癌症）的發生相互關聯甚至還是其直接的致病誘因。比如，《我不是葯神》電影中提到的慢粒白血病，它就和基因組的結構性變異直接相關。它是由於細胞中的9號染色體長臂與22號染色體長臂相互易位，導致ABL基因和BCR基因融合，形成了一個會導致ABL異常表達的小型染色體（稱為費城染色體）發生的。這是一個典型的結構性變異致癌的例子。

『陸』 序列比對結果的一根線是啥意思

這是一種序列比對在線工具。
從早期序列比對工具Needleman-Wunsch、Smith-Waterman到後來的Clustal演算法,以及近幾年的Muscle、MAFFT序列比對演算法。演算法在向更快、更精確。
為確定兩個或多個序列之間的相似性以至於同源性，而將它們按照一定的規律排列。將兩個或多個序列排列在一起，標明其相似之處。序列中可以插入間隔（通常用短橫線「-」表示）。

『柒』 基於動態規劃思想的雙序列比對演算法的全部可執行代碼將不勝感激！

你可以到google上面查一下,第一頁就有.

『捌』 smith waterman演算法中的動態規劃怎麼實現

下載軟體解決

『玖』 高中生物短序列是什麼

基因組中由寡核苷酸串聯,重復排列的DNA序列,構成數量可變的串聯重復序列,其中,微衛星DNA又稱為短串聯重復片列，是一種可遺傳的不穩定的且具有高度多態性的短核苷酸重復序列,具有種類多,分布廣,高度多態性等特點,這種多態性標志已廣泛用於遺傳病及親子鑒定等.
短序列比對中，一般常用的演算法主要有三個：
（1） 空位種子片段索引法，如MAQ、ELAND等，首先將讀段切分，並選取其中一段或幾段作為種子建立搜索索引，再通過查找索引、延展匹配來實現讀段定位，通過輪換種子考慮允許出現錯配（mismatch）的各種可能的位置組合；
（2） Burrows Wheeler轉換法，如Bowtie、BWA、SOAP2等，通過B-W轉換將基因組序列按一定規則壓縮並建立索引，再通過查找和回溯來定位讀段，在查找時可通過鹼基替代來實現允許的錯配；
（3） Smith-Waterman動態規劃演算法，如BFAST，SHRiMP等，利用初始條件和迭代關系式計算兩個序列的所有可能的比對分值，並將結果存放於一個矩陣中，利用動態規劃的方法回溯尋找最優的比對結果。