面试题：Ruby生物信息学处理之序列比对

Question

在生物信息学中，序列比对是重要操作。给定两个DNA序列字符串，使用Ruby实现一个简单的全局序列比对算法（例如Needleman - Wunsch算法），返回比对得分和比对后的序列对，并解释算法的核心步骤及如何在Ruby中实现这些步骤。

Answer 1

1. Needleman - Wunsch算法核心步骤

1. 初始化得分矩阵：创建一个二维数组（矩阵），其大小为 (m + 1) x (n + 1)，其中 m 和 n 分别是两个序列的长度。矩阵的第一行和第一列初始化为 0，代表从空序列比对到另一个序列的得分。
2. 填充得分矩阵：根据匹配、错配和空位罚分规则，使用动态规划方法填充得分矩阵。对于矩阵中的每个单元格 (i, j)，计算其得分，得分来源可能是左方 (i, j - 1)、上方 (i - 1, j) 或左上方 (i - 1, j - 1) 单元格的得分加上相应的匹配/错配/空位罚分。
3. 回溯：从得分矩阵的右下角开始，根据得分来源方向回溯，构建比对后的序列对。回溯过程依据匹配、错配和空位情况选择相应的路径，直到回到矩阵左上角。

2. Ruby 实现代码

def needleman_wunsch(seq1, seq2, match_score: 1, mismatch_score: -1, gap_score: -2)
  m, n = seq1.length, seq2.length
  # 初始化得分矩阵
  score_matrix = Array.new(m + 1) { Array.new(n + 1, 0) }
  (1..m).each do |i|
    score_matrix[i][0] = score_matrix[i - 1][0] + gap_score
  end
  (1..n).each do |j|
    score_matrix[0][j] = score_matrix[0][j - 1] + gap_score
  end
  # 填充得分矩阵
  (1..m).each do |i|
    (1..n).each do |j|
      match = score_matrix[i - 1][j - 1] + (seq1[i - 1] == seq2[j - 1]? match_score : mismatch_score)
      delete = score_matrix[i - 1][j] + gap_score
      insert = score_matrix[i][j - 1] + gap_score
      score_matrix[i][j] = [match, delete, insert].max
    end
  end
  # 回溯构建比对序列
  aligned_seq1 = ''
  aligned_seq2 = ''
  i, j = m, n
  while i > 0 || j > 0
    if i > 0 && j > 0 && score_matrix[i][j] == score_matrix[i - 1][j - 1] + (seq1[i - 1] == seq2[j - 1]? match_score : mismatch_score)
      aligned_seq1 = seq1[i - 1] + aligned_seq1
      aligned_seq2 = seq2[j - 1] + aligned_seq2
      i -= 1
      j -= 1
    elsif i > 0 && score_matrix[i][j] == score_matrix[i - 1][j] + gap_score
      aligned_seq1 = seq1[i - 1] + aligned_seq1
      aligned_seq2 = '-' + aligned_seq2
      i -= 1
    else
      aligned_seq1 = '-' + aligned_seq1
      aligned_seq2 = seq2[j - 1] + aligned_seq2
      j -= 1
    end
  end
  return score_matrix[m][n], [aligned_seq1, aligned_seq2]
end

3. 调用示例

seq1 = "AGTACGCA"
seq2 = "TATGC"
score, aligned_seqs = needleman_wunsch(seq1, seq2)
puts "比对得分: #{score}"
puts "比对后的序列对: #{aligned_seqs}"

以上代码首先按照 Needleman - Wunsch 算法的步骤初始化和填充得分矩阵，然后通过回溯构建比对后的序列对，并返回比对得分和比对后的序列对。