生物信息学_玉泉路_课堂笔记_03 第三章 多序列比对与系统发生树构建

**生物信息学_玉泉路_课堂笔记_03**

**第三章 多序列比对与系统发生树构建**

###3.1 多序列比对的基本概念多序列比对是指将两个或以上的序列进行比较，以找出它们之间的相似性和差异性的过程。这种技术在生物信息学中非常重要，因为它可以帮助我们理解蛋白质结构、功能以及进化关系。

###3.2 多序列比对算法常用的多序列比对算法包括：

* **Needleman-Wunsch算法**：该算法是最早的全局优化多序列比对算法，能够找到两个序列之间的最长公共子序列。
* **Smith-Waterman算法**：该算法是一种局部优化多序列比对算法，能够找到两个序列之间的最长公共子序列。
* **BLAST算法**：该算法是最流行的全局优化多序列比对算法，能够快速找到相似序列。

###3.3 系统发生树构建系统发生树（Phylogenetic Tree）是指描述生物进化关系的一种图形表示。系统发生树可以帮助我们理解生物之间的进化关系、共同祖先以及演化过程。

常用的系统发生树构建方法包括：

* **距离矩阵法**：该方法通过计算序列之间的距离来构建系统发生树。
* **分支长度法**：该方法通过计算序列之间的分支长度来构建系统发生树。
* **最大似然法**：该方法通过最大化似然度来构建系统发生树。

###3.4 Python代码示例

import numpy as npfrom scipy import optimize# 定义一个多序列比对函数def multi_sequence_alignment(seq1, seq2):
 # 使用Needleman-Wunsch算法进行多序列比对 gap_penalty = -1 match_reward =1 mismatch_penalty = -1 m, n = len(seq1), len(seq2)
 dp = np.zeros((m +1, n +1))
 for i in range(m +1):
 dp[i,0] = gap_penalty * i for j in range(n +1):
 dp[0, j] = gap_penalty * j for i in range(1, m +1):
 for j in range(1, n +1):
 match = dp[i -1, j -1] + (match_reward if seq1[i -1] == seq2[j -1] else mismatch_penalty)
 delete = dp[i -1, j] + gap_penalty insert = dp[i, j -1] + gap_penalty dp[i, j] = max(match, delete, insert)
 # 回溯找到多序列比对结果 i, j = m, n result = ''
 while i >0 or j >0:
 match = dp[i -1, j -1] + (match_reward if seq1[i -1] == seq2[j -1] else mismatch_penalty)
 delete = dp[i -1, j] + gap_penalty insert = dp[i, j -1] + gap_penalty if match == dp[i, j]:
 result += seq1[i -1]
 i -=1 j -=1 elif delete == dp[i, j]:
 result += '-'
 i -=1 else:
 result += '-'
 j -=1 return result[::-1]

# 测试多序列比对函数seq1 = 'ATCG'
seq2 = 'ACGT'

result = multi_sequence_alignment(seq1, seq2)
print(result)

javaimport java.util.Arrays;

public class Main {
 public static void main(String[] args) {
 String seq1 = "ATCG";
 String seq2 = "ACGT";

 System.out.println(multiSequenceAlignment(seq1, seq2));
 }

 public static String multiSequenceAlignment(String seq1, String seq2) {
 int m = seq1.length();
 int n = seq2.length();

 int[][] dp = new int[m +1][n +1];

 for (int i =0; i <= m; i++) {
 dp[i][0] = -i;
 }
 for (int j =0; j <= n; j++) {
 dp[0][j] = -j;
 }

 for (int i =1; i <= m; i++) {
 for (int j =1; j <= n; j++) {
 int match = dp[i -1][j -1] + (seq1.charAt(i -1) == seq2.charAt(j -1) ?1 : -1);
 int delete = dp[i -1][j] -1;
 int insert = dp[i][j -1] -1;

 dp[i][j] = Math.max(Math.max(match, delete), insert);
 }
 }

 StringBuilder result = new StringBuilder();
 int i = m;
 int j = n;

 while (i >0 || j >0) {
 int match = dp[i -1][j -1] + (seq1.charAt(i -1) == seq2.charAt(j -1) ?1 : -1);
 int delete = dp[i -1][j] -1;
 int insert = dp[i][j -1] -1;

 if (match == dp[i][j]) {
 result.append(seq1.charAt(i -1));
 i--;
 j--;
 } else if (delete == dp[i][j]) {
 result.append('-');
 i--;
 } else {
 result.append('-');
 j--;
 }
 }

 return result.reverse().toString();
 }
}