信息學演算法

A. 舉出在信息學中已被證明的「最優演算法」

·····你的內容和題目是否不和諧？
第一個比較排序演算法的時間最少值可以成立在各種排序演算法上的，比如桶排堆排或者快排，對於快排這種隨機排序由於處理的數據不同或是隨即函數的原因每次排序時間是不確定的。

所以我覺得第一句和 最優演算法 沒有明確的聯系，我是學信息的。

關於演算法，高中數學不是說了演算法不是唯一的嗎？至於最優打上引號還是有一些的我參考演算法導論給你一些 關於搜索路徑的簡單地說就是找迷宮出口路徑的Johnson頂點間的最短路徑演算法。
圖演算法中最小生成樹的Lruskal和Prim演算法

對於你的核心問題還是抱有疑問，一個問題有很多種演算法可以解決，而一個演算法能解決一類問題。你說你要從10個數中找出最小的，一定是從第一個找到最後一個，確實這是時間最優，但並不是空間最優，於是你的問題所謂的最優演算法還是很難肯定一個演算法是否是最優的，你在比如說用來測試CPU浮點運算速度的求pi值的演算法有很多據我所知有3種，哪一種是最優的我無法確定。

所以若不是對某一特定的問題，而是處理某一類問題的時候，是要看演算法的平均性能的。
你所謂的最優演算法，也許是存在的，但是我無法找出答案，很抱歉 如果你看到我的解答，情做你該做的事。

B. 序列比對演算法

序列比對演算法是生物信息學領域中不可或缺的一部分，其主要目標是尋找序列之間的相似性，這在資料庫搜索、基因組分析和功能預測等應用中極為重要。在序列比較過程中，理解和掌握相似性、同源性概念以及序列比較的指標和演算法對於深入研究生物序列分析至關重要。

序列比較的基本概念涉及由ATCG（RNA為AUCG）組成的核酸序列和由氨基酸縮寫組成的蛋白質序列。這些序列通常以FASTA格式存儲，如圖1所示，其中第一行為序列名稱或注釋，之後為序列主體，每行60-80個字母，具體格式根據資料庫和文件類型而定。

在序列比較中，相似性與同源性是核心概念。相似性是指通過演算法或工具快速找到序列間的相似之處，這在大型資料庫中尤為關鍵。同源性則表明兩個序列具有共同的祖先，意味著它們在結構和功能上可能存在相似之處。通過序列的相似性，我們可以推斷未知序列的結構和功能，這是蛋白質功能預測等研究領域的重要工具。

同源性可以分為直系同源和旁系同源。直系同源是指不同物種間共享的序列，來源於同一個祖先序列；旁系同源則指由於物種內部基因復制而產生的序列差異。例如，人α珠蛋白、β珠蛋白和肌紅蛋白為旁系同源，而它們的基因也是旁系同源。

序列比較的指標包括一致度和相似度。一致度描述了在相同長度的序列中，對應位置上相同殘基的比例，而相似度則考慮了替換積分矩陣（subsitution matrix）統計的不同位置殘基之間的相似性量化關系。在計算相似度時，還需考慮序列不同長度的問題，通過引入空位罰分制度，使不同長度序列對齊後進行比較。

DNA序列替換記分矩陣包括等價矩陣、轉換—顛換矩陣和BLAST矩陣。等價矩陣簡單地以相同鹼基為正，不同鹼基為零，但由於其不考慮鹼基的理化信息，實際應用較少。轉換—顛換矩陣根據轉換和顛換發生的頻率不同，給予相應得分數，而BLAST矩陣則基於大量實際比對結果，優化了轉換和顛換的得分。

蛋白質替換記分矩陣主要有等價矩陣、PAM矩陣、BLOSUM矩陣、遺傳密碼矩陣和疏水矩陣。等價矩陣與DNA替換矩陣類似，簡單地以相同氨基酸為正，不同氨基酸為零。PAM矩陣基於進化原理，反映了自然界易接受的氨基酸替換頻率。BLOSUM矩陣則通過統計相似度大於特定閾值的序列，得到更為精確的替換得分矩陣。遺傳密碼矩陣和疏水矩陣則分別從密碼子變化和氨基酸疏水性變化的角度考慮序列的相似性。

雙序列比對操作實例展示了如何使用蛋白質序列比對網站，如Pairwise Sequence Alignment，結合選擇的替換記分矩陣，對人血紅蛋白的α和β亞基進行比對。通過計算得到的相似度、一致度和最終比對得分，有助於理解序列間的相似性和同源性。

序列比對的演算法包括打分矩陣法、動態規劃模型和Blast演算法。打分矩陣法通過枚舉所有可能的比對組合來尋找最優解。動態規劃模型則通過構建狀態轉移矩陣，以動態規劃的思想逐步求解最優比對路徑。Blast演算法則採用種子-延伸策略，快速查找局部相似性，並評估比對的顯著性，通過E值衡量隨機匹配的可能性。

全局比對和局部比對的區別在於，全局比對旨在尋找序列間的整體最優匹配，而局部比對則關注於識別具有高度相似性的局部序列區域。空位罰分的改進通過引入狀態的概念，使得動態規劃模型在空位開始與空位延伸之間進行更精確的區分。

BLAST演算法是序列比對的常用方法，它首先找到高度相似的種子片段，以此為基礎向兩端擴展比對，並通過統計顯著性評估比對質量，以避免假陽性結果。此外，BLAST還採取了屏蔽低復雜度區域和考慮相似鄰居words等策略，以提高速度和靈敏度。

隱馬爾可夫鏈（HMM）在序列比對中進一步引入了生成概率的概念，使得模型不僅考慮狀態轉移概率，還能預測觀察到的符號序列，從而在比對過程中提供更精確的分析。

綜上所述，序列比對演算法是生物信息學中的一項關鍵技術，通過理解相似性、同源性概念以及序列比較指標，結合不同演算法和策略，可以高效地分析和理解生物序列之間的關系，對生物功能預測、基因組比較和進化研究等領域具有重要意義。

C. 從零開始生物信息學(2):序列比對-Needleman-Wunsch演算法

在生物信息學領域中，基因組測序的關鍵技術之一便是基因組比對，這涉及序列比對，適用於基因組序列、RNA轉錄序列及蛋白質序列等。序列比對是將兩個或多個序列按照鹼基排列進行比較，以揭示片段間的相似性，並闡明序列的同源性。這一過程尤其側重於將未知功能的序列與已知序列進行比較，以確定序列分析。序列比對的基本思想基於生物學規律，即序列決定結構，結構決定功能。將核酸序列和蛋白質一級結構看作由基本字元組成的字元串，通過檢測序列之間的相似性，可以發現生物序列中的功能、結構和進化信息。

序列比對分為雙序列比對與多序列比對。多序列比對是雙序列比對的擴展，難度更大，因此本文將主要講解雙序列比對演算法。雙序列比對演算法中，一種基於全局匹配的演算法是Needleman-Wunsch演算法。該演算法採用動態規劃演算法原理，旨在解決序列比對問題。

在序列比對過程中，對於兩種相似序列的DNA復制，有三種情況可能導致序列差異：替換、插入或刪除。相應地，序列比對存在三種可能性：完全匹配、替換或插入/刪除。為了評估不同錯誤的發生產生的比對損失，需要設定懲罰准則。例如，我們認為SNP出現的可能性較高，則對MISMATCH的懲罰較高。

基於懲罰准則，我們定義：匹配MATCH得1分，MISMATCH或GAP記-1分。理想情況下，兩個序列完全匹配時，得分為最高，而所有GAP情況最多會導致序列長度為M+N（M、N為兩個序列長度）的匹配。理想得分最低，但採用窮舉法計算最優比對分數過於耗時。因此，需要演算法高效計算最優比對分數。

動態規劃演算法通過將復雜問題分解為簡單子問題的方法來解決問題，確保子結構最優，從而全局最優。以下是Needleman-Wunsch演算法的步驟概述與實例解析。

初始化得分矩陣：創建一個矩陣用於比對回溯，矩陣的行列分別代表兩個序列的鹼基排列，第一行與第一列為懲罰得分，按照0、-1、-2排列，以反映相鄰位點的GAP成本。計算得分矩陣時，從左上到右下的順序進行，每個位點的得分基於與它相鄰位置的得分相關。具體計算方法如下：每個位點得分等於左上、上方與左方三個方向最大得分加上移動過程得分。最終，選擇三個方向中最高得分作為該位點得分，並重復此過程直至完成矩陣計算。

利用得分矩陣，我們可以計算出最優比對分數。但為了獲取最終比對結果，還需回溯得分矩陣，找出最優路徑。回溯方式如下：查看每個回溯位點的左上方、上方和左方最大得分位置，以此得到回溯路徑。通過從右下角開始，根據最大得分所在方向決定引入GAP或取用鹼基，最終可得到兩段序列比對結果。

通過上述流程，我們可以得到比對得分最高的比對結果。為了進一步理解，讀者可以自行按照公式進行流程實踐。如果在學習過程中遇到問題，歡迎與作者交流。此外，作者歡迎讀者關注其知乎專欄「從零開始生物信息學」和微信公眾號「壹讀基因」。