信息学算法

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或取用碱基，最终可得到两段序列比对结果。

通过上述流程，我们可以得到比对得分最高的比对结果。为了进一步理解，读者可以自行按照公式进行流程实践。如果在学习过程中遇到问题，欢迎与作者交流。此外，作者欢迎读者关注其知乎专栏“从零开始生物信息学”和微信公众号“壹读基因”。