算法与数据结构基础¶
一句话说明：算法是解决问题的步骤，数据结构是组织数据的方式——掌握它们，你就能写出高效代码、看懂生信工具原理、通过技术面试。
为什么要学算法与数据结构？¶
面试常考：几乎所有技术岗面试都会考算法题，生信岗也不例外。面试官通过算法题判断你的逻辑思维和编程能力。
写高效代码：同样的任务，用对数据结构可能从跑 10 小时变成 10 分钟。比如用哈希表做 k-mer 计数，比逐一比对快几万倍。
理解工具原理：BWA 用后缀数组做序列比对、SPAdes 用 de Bruijn 图做基因组组装、BLAST 用动态规划做序列比对——不懂算法，这些工具对你就是黑箱。
白话说：算法就像做菜的菜谱，数据结构就像你厨房里的锅碗瓢盆。菜谱再好，没有合适的锅也做不了菜；锅再好，没有菜谱也不知道怎么做。
一、时间复杂度与空间复杂度¶
在讲数据结构之前，先搞懂"快慢"怎么衡量。
白话解释¶
时间复杂度 = 数据量变大时，程序运行时间怎么增长。
空间复杂度 = 数据量变大时，程序占用内存怎么增长。
用大 O 表示法（Big O）：
| 复杂度 | 白话解释 | 例子 |
|---|---|---|
| O(1) | 不管数据多大，时间固定。就像查字典直接翻到那一页 | 字典按 key 取值 |
| O(log n) | 数据翻倍，时间只多一步。就像猜数字每次猜中间 | 二分查找 |
| O(n) | 数据翻倍，时间也翻倍。就像挨个数一排人 | 遍历列表 |
| O(n log n) | 比 O(n) 慢一点，大多数高效排序的速度 | 快速排序、归并排序 |
| O(n²) | 数据翻倍，时间变 4 倍。就像所有人互相握手 | 冒泡排序、两层循环 |
| O(2ⁿ) | 每多一个数据，时间翻倍。指数爆炸 | 暴力穷举所有子集 |
生信实际感受：处理 100 万条序列时—— - O(n) 算法：100 万步，秒级完成 - O(n²) 算法：1 万亿步，可能跑几天 - O(n log n) 算法：2000 万步，几秒搞定
# === 复杂度直观演示 ===
import time # 导入时间模块
def demo_o1(data):
"""O(1)：常数时间——不管列表多长，只取第一个"""
return data[0] # 直接按索引取值，一步到位
def demo_on(data):
"""O(n)：线性时间——数据翻倍，时间翻倍"""
total = 0 # 初始化累加器
for x in data: # 遍历每一个元素
total += x # 累加
return total # 返回总和
def demo_on2(data):
"""O(n²)：平方时间——两层循环，数据翻倍时间变4倍"""
count = 0 # 初始化计数器
for i in data: # 外层循环
for j in data: # 内层循环（对每个i都遍历全部j）
count += 1 # 每一对(i,j)都计数
return count # 返回总配对数
# 测试不同规模
for size in [1000, 5000, 10000]: # 逐步增大数据量
data = list(range(size)) # 生成测试数据
start = time.time() # 记录开始时间
demo_on(data) # 运行O(n)
t_n = time.time() - start # 计算耗时
start = time.time() # 记录开始时间
demo_on2(data) # 运行O(n²)
t_n2 = time.time() - start # 计算耗时
print(f"n={size:>6}: O(n)={t_n:.6f}s, O(n²)={t_n2:.6f}s")
# 你会看到 n 翻 5 倍时，O(n) 耗时翻 5 倍，O(n²) 耗时翻 25 倍
二、核心数据结构¶
2.1 列表 / 数组（List / Array）¶
白话：一排编了号的格子，按编号（索引）存取东西。就像一排储物柜，每个柜子有编号。
时间复杂度： - 按索引访问：O(1) - 末尾添加：O(1)（均摊） - 插入/删除中间元素：O(n)（后面的都要挪位） - 查找某个值：O(n)
# === 列表基本操作 ===
genes = ["BRCA1", "TP53", "EGFR", "KRAS"] # 创建基因列表
# 按索引访问——O(1)，直接跳到第2个位置
print(genes[1]) # 输出: TP53
# 末尾添加——O(1)
genes.append("MYC") # 在最后面加一个基因
print(genes) # ['BRCA1', 'TP53', 'EGFR', 'KRAS', 'MYC']
# 中间插入——O(n)，后面的元素都要往后挪
genes.insert(2, "PIK3CA") # 在索引2的位置插入
print(genes) # ['BRCA1', 'TP53', 'PIK3CA', 'EGFR', 'KRAS', 'MYC']
# 遍历——O(n)
for i, gene in enumerate(genes): # enumerate 同时给出索引和值
print(f"索引{i}: {gene}") # 打印每个基因及其位置
# 列表推导式——Python特色的高效写法
lengths = [len(g) for g in genes] # 计算每个基因名的长度
print(lengths) # [5, 4, 6, 4, 4, 3]
# 切片操作——取子列表
top3 = genes[:3] # 取前3个元素
print(top3) # ['BRCA1', 'TP53', 'PIK3CA']
生信应用：存储序列、质量分数（FASTQ 的 quality scores）、基因表达矩阵的一行数据。
2.2 字典 / 哈希表（Dict / Hash Table）¶
白话：一本"索引册"，通过名字（key）直接查到内容（value）。就像通讯录，知道名字就能查到电话号码，不需要从头翻。
时间复杂度： - 查找/插入/删除：O(1)（平均） - 遍历所有：O(n)
# === 字典基本操作 ===
# 基因 -> 功能的映射
gene_function = { # 创建字典
"BRCA1": "DNA修复", # key: value 对
"TP53": "肿瘤抑制",
"EGFR": "细胞增殖信号",
}
# 查找——O(1)，直接通过key定位
print(gene_function["TP53"]) # 输出: 肿瘤抑制
# 添加——O(1)
gene_function["KRAS"] = "信号转导" # 新增一个键值对
# 安全查找——key不存在时不报错
result = gene_function.get("BRAF", "未知功能") # 找不到就返回默认值
print(result) # 输出: 未知功能
# 遍历所有键值对
for gene, func in gene_function.items(): # .items() 返回键值对
print(f"{gene}: {func}")
# === 生信实战：k-mer 计数 ===
def count_kmers(sequence, k):
"""统计序列中所有长度为k的子串出现次数"""
kmer_counts = {} # 空字典，用来存计数结果
for i in range(len(sequence) - k + 1): # 滑动窗口遍历
kmer = sequence[i:i+k] # 截取长度为k的子串
# 如果这个kmer已经见过，计数+1；没见过就初始化为1
kmer_counts[kmer] = kmer_counts.get(kmer, 0) + 1
return kmer_counts # 返回计数字典
seq = "ATCGATCGATCG" # 测试序列
result = count_kmers(seq, 3) # 统计3-mer
print(result) # {'ATC': 3, 'TCG': 3, 'CGA': 2, 'GAT': 2}
# 哈希表让每次查找和更新都是O(1)，处理百万序列也很快
生信应用：k-mer 计数、基因 ID 映射、GO 注释查询、样本元数据存储。这是生信中最常用的数据结构。
2.3 集合（Set）¶
白话：一个"去重袋子"，扔东西进去自动去重，查某个东西在不在也特别快。就像签到表，只记名字不记顺序，来过就标记了。
时间复杂度： - 查找/添加/删除：O(1)（平均） - 求交集：O(min(m, n))，并集：O(m+n)，差集：O(m)（m 为被减集合大小）
# === 集合基本操作 ===
# 两个样本中检测到的基因集合
sample_a = {"BRCA1", "TP53", "EGFR", "KRAS", "MYC"} # 样本A的基因
sample_b = {"TP53", "EGFR", "PIK3CA", "BRAF", "MYC"} # 样本B的基因
# 交集——两个样本共有的基因
common = sample_a & sample_b # & 是交集运算符
print(f"共有基因: {common}") # {'TP53', 'EGFR', 'MYC'}
# 并集——两个样本所有出现过的基因
all_genes = sample_a | sample_b # | 是并集运算符
print(f"所有基因: {all_genes}")
# 差集——样本A有但B没有的基因
a_only = sample_a - sample_b # - 是差集运算符
print(f"A独有: {a_only}") # {'BRCA1', 'KRAS'}
# 成员判断——O(1)，非常快
print("BRCA1" in sample_a) # True——在集合中查找是O(1)
print("BRCA1" in ["BRCA1", "TP53"]) # True——但在列表中查找是O(n)
# === 实战：从大列表中去重 ===
raw_reads = ["ATCG", "GCTA", "ATCG", "TTTT", "GCTA", "ATCG"] # 原始reads，有重复
unique_reads = set(raw_reads) # 一行去重
print(f"去重前: {len(raw_reads)}, 去重后: {len(unique_reads)}")
# 去重前: 6, 去重后: 3
生信应用：基因列表去重、差异基因集合的韦恩图运算、快速判断某基因是否在已知基因库中。
2.4 栈和队列（Stack & Queue）¶
白话： - 栈（Stack）：像叠盘子，后放的先拿（后进先出，LIFO） - 队列（Queue）：像排队买饭，先来的先走（先进先出，FIFO）
时间复杂度：入栈/出栈、入队/出队都是 O(1)。
# === 栈——用列表实现 ===
stack = [] # 空栈
stack.append("第1步: 读取FASTQ") # 压入栈（push）
stack.append("第2步: 质控") # 压入栈
stack.append("第3步: 比对") # 压入栈
print(stack.pop()) # 弹出栈顶（pop）: "第3步: 比对"
print(stack.pop()) # 弹出: "第2步: 质控"
# 栈的应用：函数调用栈、撤销操作、括号匹配
# === 队列——用 collections.deque 实现 ===
from collections import deque # deque 是双端队列，两头操作都是O(1)
task_queue = deque() # 创建空队列
task_queue.append("样本001") # 入队（队尾加入）
task_queue.append("样本002") # 入队
task_queue.append("样本003") # 入队
print(task_queue.popleft()) # 出队（队首弹出）: "样本001"
print(task_queue.popleft()) # 出队: "样本002"
# 队列的应用：任务调度、BFS搜索、流水线处理
生信应用：分析流水线的任务调度（先提交的样本先处理）、BFS 遍历基因调控网络、递归调用栈。
2.5 链表（Linked List）¶
白话：一串珠子，每颗珠子知道下一颗在哪。不像数组那样连续存放，而是"串"起来的。好处是插入删除快（O(1)），坏处是不能直接跳到第 N 个（得从头数，O(n)）。
时间复杂度： - 头部插入/删除：O(1) - 按索引访问：O(n) - 查找：O(n)
# === 简单链表实现 ===
class Node:
"""链表节点：每个节点存一个值和指向下一个节点的指针"""
def __init__(self, data):
self.data = data # 节点存储的数据
self.next = None # 指向下一个节点的指针，初始为空
class LinkedList:
"""单向链表"""
def __init__(self):
self.head = None # 链表头部，初始为空
def prepend(self, data):
"""在头部插入——O(1)"""
new_node = Node(data) # 创建新节点
new_node.next = self.head # 新节点指向原来的头
self.head = new_node # 更新头部为新节点
def display(self):
"""遍历打印——O(n)"""
current = self.head # 从头开始
items = [] # 收集所有值
while current: # 一直走到末尾（None）
items.append(current.data) # 记录当前值
current = current.next # 移动到下一个
print(" -> ".join(items)) # 用箭头连接打印
# 使用链表
pipeline = LinkedList() # 创建空链表
pipeline.prepend("比对") # 插入到头部
pipeline.prepend("质控") # 插入到头部（变成第一个）
pipeline.prepend("读取") # 插入到头部（变成第一个）
pipeline.display() # 输出: 读取 -> 质控 -> 比对
生信应用：基因组上的变异位点链表、流水线步骤的链式调用。实际开发中 Python 直接用 list 更多，但面试常考链表操作。
2.6 树（Tree）¶
白话：倒过来的树——最上面是根，往下分叉。每个节点可以有子节点。
- 二叉树：每个节点最多 2 个孩子（左、右）
- 二叉搜索树（BST）：左孩子比自己小，右孩子比自己大，查找很快
- B 树 / B+ 树：数据库索引用的多叉树，磁盘读取效率高
# === 二叉搜索树实现 ===
class TreeNode:
"""树节点"""
def __init__(self, val):
self.val = val # 节点值
self.left = None # 左子节点
self.right = None # 右子节点
class BST:
"""二叉搜索树：左小右大"""
def __init__(self):
self.root = None # 根节点
def insert(self, val):
"""插入值——O(log n) 平均"""
if not self.root: # 空树，直接设为根
self.root = TreeNode(val)
return
self._insert(self.root, val) # 递归插入
def _insert(self, node, val):
"""递归找到合适位置插入"""
if val < node.val: # 比当前节点小，往左走
if node.left is None: # 左边为空，就插在这里
node.left = TreeNode(val)
else:
self._insert(node.left, val) # 左边不空，继续往左找
else: # 比当前节点大或等于，往右走
if node.right is None: # 右边为空，就插在这里
node.right = TreeNode(val)
else:
self._insert(node.right, val) # 右边不空，继续往右找
def search(self, val):
"""查找值——O(log n) 平均"""
return self._search(self.root, val)
def _search(self, node, val):
"""递归查找"""
if node is None: # 走到空了，没找到
return False
if val == node.val: # 找到了
return True
elif val < node.val: # 目标比当前小，往左找
return self._search(node.left, val)
else: # 目标比当前大，往右找
return self._search(node.right, val)
def inorder(self, node, result=None):
"""中序遍历——会得到从小到大的排序结果"""
if result is None:
result = [] # 初始化结果列表
if node:
self.inorder(node.left, result) # 先遍历左子树
result.append(node.val) # 再访问当前节点
self.inorder(node.right, result) # 最后遍历右子树
return result
# 使用二叉搜索树
bst = BST()
expression_values = [5.2, 3.1, 7.8, 1.0, 4.5, 6.3, 9.9] # 基因表达量
for val in expression_values: # 逐个插入
bst.insert(val)
print(bst.search(4.5)) # True——O(log n) 查找
print(bst.inorder(bst.root)) # [1.0, 3.1, 4.5, 5.2, 6.3, 7.8, 9.9]——排好序了
生信应用：物种进化树（系统发育树）本质就是树结构；数据库索引用 B+ 树加速查询；决策树/随机森林也是树。
2.7 图（Graph）¶
白话：一堆点（节点）和连接它们的线（边）。比树更自由——任意两个节点之间都可以连线，还可以有方向和权重。
# === 用字典表示图（邻接表） ===
# 蛋白质互作网络（PPI Network）
ppi_network = { # 每个蛋白质 -> 与它互作的蛋白质列表
"TP53": ["MDM2", "BRCA1", "ATM"], # TP53 和这3个蛋白质有互作
"BRCA1": ["TP53", "RAD51", "BARD1"],
"MDM2": ["TP53"],
"ATM": ["TP53", "BRCA1"],
"RAD51": ["BRCA1"],
"BARD1": ["BRCA1"],
}
# 查找某个蛋白质的互作伙伴——O(1)
print(f"TP53的互作: {ppi_network['TP53']}")
# 计算每个蛋白质的度（degree = 连接数）
for protein, partners in ppi_network.items():
print(f"{protein}: degree = {len(partners)}")
# TP53 degree=3，是这个网络中的 hub 蛋白（连接最多）
# 判断两个蛋白质是否有直接互作
def has_interaction(network, protein_a, protein_b):
"""判断两个蛋白质是否直接互作"""
if protein_a in network: # 先确保蛋白质a在网络中
return protein_b in network[protein_a] # 判断b是否在a的邻居中
return False
print(has_interaction(ppi_network, "TP53", "MDM2")) # True
print(has_interaction(ppi_network, "RAD51", "MDM2")) # False
生信应用：蛋白质互作网络（PPI）、基因调控网络（GRN）、代谢通路网络、de Bruijn 图（基因组组装的核心）。
三、核心算法¶
3.1 排序算法¶
快速排序（Quick Sort）¶
白话：选一个基准值，比它小的放左边，比它大的放右边，然后对左右两边分别再排。像打牌时按大小分堆再整理。
时间复杂度：平均 O(n log n)，最坏 O(n²)
def quick_sort(arr):
"""快速排序——分而治之"""
if len(arr) <= 1: # 0或1个元素不用排，直接返回
return arr
pivot = arr[len(arr) // 2] # 选中间的元素作为基准
left = [x for x in arr if x < pivot] # 比基准小的放左边
middle = [x for x in arr if x == pivot] # 等于基准的放中间
right = [x for x in arr if x > pivot] # 比基准大的放右边
return quick_sort(left) + middle + quick_sort(right) # 递归排序后拼接
# 测试：按表达量排序基因
expression = [5.2, 1.1, 8.7, 3.3, 6.6, 2.2] # 基因表达量
sorted_exp = quick_sort(expression) # 排序
print(sorted_exp) # [1.1, 2.2, 3.3, 5.2, 6.6, 8.7]
归并排序（Merge Sort）¶
白话：先把数组拆成两半，分别排好序，再合并。像两副已排好的扑克牌，按大小交替合在一起。
时间复杂度：始终 O(n log n)，稳定排序
def merge_sort(arr):
"""归并排序——先拆后合"""
if len(arr) <= 1: # 一个元素不用排
return arr
mid = len(arr) // 2 # 找中间位置
left = merge_sort(arr[:mid]) # 递归排序左半部分
right = merge_sort(arr[mid:]) # 递归排序右半部分
return merge(left, right) # 合并两个有序数组
def merge(left, right):
"""合并两个有序数组"""
result = [] # 存放合并结果
i = j = 0 # 两个指针分别指向left和right的开头
while i < len(left) and j < len(right): # 两边都还有元素
if left[i] <= right[j]: # 左边当前元素更小
result.append(left[i]) # 放入结果
i += 1 # 左指针前进
else: # 右边当前元素更小
result.append(right[j]) # 放入结果
j += 1 # 右指针前进
result.extend(left[i:]) # 左边剩余的全部放入
result.extend(right[j:]) # 右边剩余的全部放入
return result
# 测试
data = [38, 27, 43, 3, 9, 82, 10] # 待排序数据
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
生信应用：SAMtools sort 对 BAM 文件按坐标排序、对差异基因按 p-value 排序。
3.2 二分查找（Binary Search）¶
白话：在一个已排好序的列表中，每次比较中间的元素，如果目标比中间小就去左半边找，比中间大就去右半边找。每一步排除一半，非常快。
时间复杂度：O(log n)
def binary_search(arr, target):
"""二分查找——前提是数组已排序"""
left, right = 0, len(arr) - 1 # 左右边界
while left <= right: # 还有搜索空间
mid = (left + right) // 2 # 取中间位置
if arr[mid] == target: # 正好找到
return mid # 返回索引
elif arr[mid] < target: # 中间值太小，目标在右半边
left = mid + 1 # 移动左边界
else: # 中间值太大，目标在左半边
right = mid - 1 # 移动右边界
return -1 # 没找到
# 测试：在排好序的染色体位置中查找
positions = [100, 250, 500, 750, 1000, 1500, 2000, 3000] # 已排序的变异位点
idx = binary_search(positions, 750) # 查找位置750
print(f"找到位置750在索引: {idx}") # 输出: 3
print(f"查找999: {binary_search(positions, 999)}") # 输出: -1（没找到）
生信应用：在排好序的 BAM 文件中按坐标快速定位 reads、tabix 索引查询。
3.3 双指针（Two Pointers）¶
白话：用两个指针从不同位置出发，协同移动来解决问题。就像两个人从绳子两头往中间走。
def two_sum_sorted(arr, target):
"""在有序数组中找两个数的和等于target"""
left, right = 0, len(arr) - 1 # 左右两个指针
while left < right: # 两个指针没相遇
current_sum = arr[left] + arr[right] # 当前两数之和
if current_sum == target: # 找到了
return (left, right) # 返回两个索引
elif current_sum < target: # 和太小，左指针右移让和变大
left += 1
else: # 和太大，右指针左移让和变小
right -= 1
return None # 没找到
# 测试：找两个表达量之和等于10
values = [1.5, 2.3, 3.7, 4.8, 6.2, 7.5, 8.1] # 已排序
result = two_sum_sorted(values, 10.0) # 找和为10的两个数
if result:
i, j = result
print(f"values[{i}]={values[i]} + values[{j}]={values[j]} = {values[i]+values[j]}")
生信应用：合并有序的基因组区间、对已排序的 reads 做配对分析。
3.4 滑动窗口（Sliding Window）¶
白话：在序列上放一个固定大小的"窗口"，每次往右滑动一格。就像火车窗户——你看到的风景是固定宽度的一段，火车动一格你就看到新的一格风景。
def gc_content_windows(sequence, window_size):
"""用滑动窗口计算序列每个区域的GC含量"""
results = [] # 存放每个窗口的GC含量
# 先算第一个窗口的GC数
gc_count = sum(1 for c in sequence[:window_size] if c in "GC")
results.append(gc_count / window_size) # 第一个窗口的GC含量
# 窗口滑动：每次减去离开窗口的碱基，加上进入窗口的碱基
for i in range(1, len(sequence) - window_size + 1):
if sequence[i - 1] in "GC": # 离开窗口的碱基是GC
gc_count -= 1 # GC计数减1
if sequence[i + window_size - 1] in "GC": # 进入窗口的碱基是GC
gc_count += 1 # GC计数加1
results.append(gc_count / window_size) # 记录当前窗口GC含量
return results
# 测试
seq = "ATCGGCTAGCTTAAGCGCTA" # 测试序列
gc_profile = gc_content_windows(seq, 5) # 窗口大小5
for i, gc in enumerate(gc_profile):
print(f"位置{i}-{i+4}: GC={gc:.1%}") # 打印每个窗口的GC含量
# 滑动窗口让每个窗口的计算是O(1)，总时间O(n)
# 如果每个窗口都重新数一遍就是O(n*k)，窗口越大越慢
生信应用：GC 含量分析、序列质量滑动窗口评估（Trimmomatic 的 SLIDINGWINDOW）、CpG 岛检测。
3.5 递归（Recursion）¶
白话：函数自己调用自己。就像俄罗斯套娃——打开一个娃娃，里面还有一个更小的娃娃，直到最小的那个（基线条件）为止。
def fibonacci(n, memo={}):
"""斐波那契数列——带记忆化的递归
注意：memo={} 利用了 Python 可变默认参数在函数调用间共享的特性来做缓存。
面试中如果被问到可变默认参数的陷阱，要能解释这里是故意利用这个行为。
更规范的写法是用 functools.lru_cache 装饰器。
"""
if n <= 1: # 基线条件：不再递归
return n
if n in memo: # 已经算过了，直接返回（避免重复计算）
return memo[n]
memo[n] = fibonacci(n - 1) + fibonacci(n - 2) # 递归调用
return memo[n]
# 测试
for i in range(10):
print(f"F({i}) = {fibonacci(i)}", end=" ")
# F(0)=0 F(1)=1 F(2)=1 F(3)=2 F(4)=3 F(5)=5 ...
print()
# === 递归遍历进化树 ===
def count_leaves(tree):
"""递归计算树的叶子节点数（物种数）"""
if isinstance(tree, str): # 叶子节点是字符串（物种名）
return 1 # 基线条件
total = 0 # 初始化计数
for subtree in tree: # 遍历每个子树
total += count_leaves(subtree) # 递归计算
return total
# 一个简单的进化树结构（嵌套列表表示）
phylo_tree = [["人类", "黑猩猩"], ["大猩猩", ["猩猩", "长臂猿"]]]
print(f"物种数: {count_leaves(phylo_tree)}") # 输出: 5
生信应用：系统发育树遍历、分治算法（归并排序、快排）、递归解析嵌套的文件格式（如 Newick 树格式）。
3.6 动态规划入门（Dynamic Programming）¶
白话：把大问题拆成小问题，记住小问题的答案（不重复计算），用小问题的答案推出大问题的答案。就像爬楼梯——到第 10 级的方法数 = 到第 9 级的方法数 + 到第 8 级的方法数。
这是生信中最重要的算法思想——序列比对的核心就是动态规划。
# === 经典动态规划：爬楼梯 ===
def climb_stairs(n):
"""爬n级楼梯，每次爬1或2级，有多少种方法？"""
if n <= 2: # 1级有1种，2级有2种
return n
dp = [0] * (n + 1) # dp[i] = 到第i级的方法数
dp[1] = 1 # 到第1级只有1种方法
dp[2] = 2 # 到第2级有2种方法（1+1 或 2）
for i in range(3, n + 1): # 从第3级开始推导
dp[i] = dp[i-1] + dp[i-2] # 从i-1跨1步 或 从i-2跨2步
return dp[n]
print(f"爬10级楼梯: {climb_stairs(10)}种方法") # 89
# === 生信核心：简化版序列比对（编辑距离） ===
def edit_distance(seq1, seq2):
"""计算两条序列的编辑距离（最少需要多少次操作变成一样）
操作包括：插入、删除、替换
这就是序列比对的简化版原理！
"""
m, n = len(seq1), len(seq2) # 两条序列的长度
# dp[i][j] = seq1前i个字符 变成 seq2前j个字符 需要的最少操作数
dp = [[0] * (n + 1) for _ in range(m + 1)] # 创建 (m+1) x (n+1) 的表
for i in range(m + 1): # 第一列：seq2为空，需要删除i次
dp[i][0] = i
for j in range(n + 1): # 第一行：seq1为空，需要插入j次
dp[0][j] = j
for i in range(1, m + 1): # 逐行填表
for j in range(1, n + 1): # 逐列填表
if seq1[i-1] == seq2[j-1]: # 当前字符相同，不需要操作
dp[i][j] = dp[i-1][j-1] # 直接继承左上角的值
else: # 当前字符不同，取三种操作的最小值 + 1
dp[i][j] = 1 + min(
dp[i-1][j], # 删除（从上方来）
dp[i][j-1], # 插入（从左方来）
dp[i-1][j-1] # 替换（从左上方来）
)
return dp[m][n] # 右下角就是最终答案
# 测试
seq1 = "ATCGTAC" # 序列1
seq2 = "ATGCTAC" # 序列2
dist = edit_distance(seq1, seq2)
print(f"'{seq1}' 和 '{seq2}' 的编辑距离: {dist}") # 2
# BLAST、Smith-Waterman、Needleman-Wunsch 都基于类似的DP思想
生信应用：Needleman-Wunsch 全局比对、Smith-Waterman 局部比对、多序列比对、隐马尔可夫模型（HMM）的 Viterbi 算法。
3.7 BFS 与 DFS（图/树遍历）¶
白话： - BFS（广度优先）：像水波扩散，一圈一圈往外走。先访问所有近邻，再访问近邻的近邻。 - DFS（深度优先）：像走迷宫，一条路走到底，走不通了再回头试另一条。
from collections import deque # BFS需要队列
# 基因调控网络
gene_network = {
"TP53": ["MDM2", "CDKN1A", "BAX"], # TP53 调控这3个基因
"MDM2": ["TP53"], # 负反馈
"CDKN1A": ["CDK2"],
"BAX": ["BCL2"],
"CDK2": [],
"BCL2": [],
}
def bfs(graph, start):
"""BFS广度优先——一层一层往外扩展"""
visited = set() # 记录已访问的节点（避免重复）
queue = deque([start]) # 初始化队列，放入起始节点
visited.add(start) # 标记起始节点为已访问
order = [] # 记录访问顺序
while queue: # 队列不为空就继续
node = queue.popleft() # 取出队首节点
order.append(node) # 记录访问顺序
for neighbor in graph.get(node, []): # 遍历所有邻居
if neighbor not in visited: # 没访问过的才加入
visited.add(neighbor) # 标记为已访问
queue.append(neighbor) # 加入队尾
return order
def dfs(graph, start, visited=None):
"""DFS深度优先——一条路走到底再回头"""
if visited is None:
visited = set() # 初始化已访问集合
visited.add(start) # 标记当前节点为已访问
order = [start] # 记录当前节点
for neighbor in graph.get(start, []): # 遍历邻居
if neighbor not in visited: # 没访问过的
order.extend(dfs(graph, neighbor, visited)) # 递归深入
return order
print(f"BFS从TP53出发: {bfs(gene_network, 'TP53')}")
# ['TP53', 'MDM2', 'CDKN1A', 'BAX', 'CDK2', 'BCL2']——一层一层
print(f"DFS从TP53出发: {dfs(gene_network, 'TP53')}")
# ['TP53', 'MDM2', 'CDKN1A', 'CDK2', 'BAX', 'BCL2']——一条路走到底
生信应用：基因调控网络分析、蛋白质互作网络的连通分量检测、代谢通路搜索、系统发育树遍历。
四、生信中的算法应用¶
4.1 动态规划 -> 序列比对¶
BLAST、BWA-MEM 的核心。Needleman-Wunsch（全局比对）和 Smith-Waterman（局部比对）都是经典 DP：构建得分矩阵，通过回溯找到最优比对路径。上面的编辑距离就是简化版。
4.2 de Bruijn 图 -> 基因组组装¶
SPAdes、MEGAHIT 把 reads 打断成 k-mer，每个 k-mer 是图的一条边，通过找欧拉路径（经过每条边恰好一次）来组装基因组。白话说：把拼图碎片按重叠部分连成网络，然后找一条路把所有碎片串起来。
4.3 后缀数组 / BWT -> 序列索引¶
BWA 用 Burrows-Wheeler Transform 建立参考基因组索引，让比对速度从 O(m*n) 降到接近 O(m)。白话说：对基因组做特殊的"排序变换"，让查找任意子串变得极快。
4.4 哈希表 -> k-mer 计数¶
Jellyfish、KMC 用哈希表存储 k-mer 及其出现次数。处理几十 GB 的测序数据时，O(1) 的查找和更新速度至关重要。
4.5 隐马尔可夫模型（HMM）¶
Prodigal 基因预测、HMMER 蛋白质家族搜索都用 HMM。核心是 Viterbi 算法（也是动态规划），在隐藏状态序列中找最优路径。
五、LeetCode 推荐入门题目¶
按难度递进，优先刷这些：
入门（Easy）¶
| 题号 | 题目 | 考点 | 生信联系 |
|---|---|---|---|
| 1 | Two Sum | 哈希表 | 快速查找配对 |
| 20 | Valid Parentheses | 栈 | 括号/标签匹配 |
| 21 | Merge Two Sorted Lists | 链表 | 合并有序数据 |
| 70 | Climbing Stairs | 动态规划 | DP入门 |
| 104 | Maximum Depth of Binary Tree | 树/递归 | 进化树遍历 |
| 141 | Linked List Cycle | 快慢指针 | 环检测 |
| 206 | Reverse Linked List | 链表 | 面试必考 |
| 704 | Binary Search | 二分查找 | 坐标索引查询 |
进阶（Medium）¶
| 题号 | 题目 | 考点 | 生信联系 |
|---|---|---|---|
| 3 | Longest Substring Without Repeating | 滑动窗口 | 序列特征扫描 |
| 15 | 3Sum | 双指针 | 多条件组合查找 |
| 53 | Maximum Subarray | 动态规划 | 信号峰值区段检测 |
| 72 | Edit Distance | DP | 序列比对核心 |
| 102 | Binary Tree Level Order | BFS | 层级遍历 |
| 200 | Number of Islands | DFS/BFS | 连通分量 |
| 322 | Coin Change | DP | 资源优化分配 |
六、常见面试算法题（6 道 + Python 解法）¶
题 1：两数之和（LeetCode #1）¶
def two_sum(nums, target):
"""给定数组和目标值，找出和为目标值的两个数的索引
思路：用哈希表记录"需要的配对值"
时间O(n)，空间O(n)
"""
seen = {} # 哈希表：值 -> 索引
for i, num in enumerate(nums): # 遍历每个数
complement = target - num # 计算需要的配对值
if complement in seen: # 配对值之前见过
return [seen[complement], i] # 返回两个索引
seen[num] = i # 记录当前值和索引
return [] # 没找到
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]——因为 2+7=9
题 2：有效括号（LeetCode #20）¶
def is_valid_parentheses(s):
"""判断括号字符串是否有效
思路：左括号压栈，右括号弹栈匹配
"""
stack = [] # 用列表模拟栈
pairs = {')': '(', ']': '[', '}': '{'} # 右括号 -> 对应的左括号
for char in s: # 遍历每个字符
if char in pairs: # 是右括号
if not stack or stack[-1] != pairs[char]: # 栈空或不匹配
return False # 无效
stack.pop() # 匹配成功，弹出栈顶
else: # 是左括号
stack.append(char) # 压入栈
return len(stack) == 0 # 最后栈空才是有效的
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("(]")) # False
题 3：反转链表（LeetCode #206）¶
class ListNode:
"""链表节点"""
def __init__(self, val=0, next=None):
self.val = val # 值
self.next = next # 下一个节点
def reverse_list(head):
"""反转链表
思路：三指针法，逐个翻转指向
"""
prev = None # 前一个节点，初始为空
curr = head # 当前节点，从头开始
while curr: # 还没到末尾
next_temp = curr.next # 先保存下一个节点（不然翻转后就丢了）
curr.next = prev # 当前节点指向前一个（翻转！）
prev = curr # 前指针前进
curr = next_temp # 当前指针前进
return prev # prev 现在是新的头节点
# 构建测试链表: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = reverse_list(head) # 反转
# 打印结果
node = new_head
while node:
print(node.val, end=" -> " if node.next else "\n") # 4 -> 3 -> 2 -> 1
node = node.next
题 4：最大子数组和（LeetCode #53）¶
def max_subarray(nums):
"""找到数组中连续子数组的最大和
思路：Kadane算法——维护当前最大和，如果加上当前数反而变小就重新开始
生信联系：找基因组上信号最强的连续区段
"""
max_sum = nums[0] # 全局最大和，初始为第一个元素
current_sum = nums[0] # 当前连续和
for i in range(1, len(nums)): # 从第二个元素开始
# 要么加上当前数继续延伸，要么从当前数重新开始
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum) # 更新全局最大
return max_sum
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6（子数组[4,-1,2,1]）
题 5：二叉树最大深度（LeetCode #104）¶
class TreeNode:
"""二叉树节点"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root):
"""计算二叉树最大深度
思路：递归——树的深度 = max(左子树深度, 右子树深度) + 1
生信联系：计算进化树的最大进化距离
"""
if root is None: # 空节点深度为0（基线条件）
return 0
left_depth = max_depth(root.left) # 递归算左子树深度
right_depth = max_depth(root.right) # 递归算右子树深度
return max(left_depth, right_depth) + 1 # 取较大的+1（加上自己这一层）
# 构建测试树: 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(f"最大深度: {max_depth(root)}") # 3
题 6：编辑距离（LeetCode #72）¶
def min_distance(word1, word2):
"""计算将word1转换为word2所需的最少操作次数
操作：插入、删除、替换
这道题就是序列比对的核心算法！
"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)] # DP表
# 初始化：空串到另一个串需要的操作数
for i in range(m + 1):
dp[i][0] = i # word1前i个字符全删除
for j in range(n + 1):
dp[0][j] = j # 空串插入j个字符
# 填表
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]: # 字符相同
dp[i][j] = dp[i-1][j-1] # 不需要操作
else: # 字符不同，三种操作取最小
dp[i][j] = 1 + min(
dp[i-1][j], # 删除word1[i]
dp[i][j-1], # 在word1中插入word2[j]
dp[i-1][j-1] # 替换word1[i]为word2[j]
)
return dp[m][n]
# 生信示例：两条DNA序列的编辑距离
print(min_distance("ATCGTAC", "ATGCTAC")) # 2
print(min_distance("GATTACA", "GCATGCU")) # 4
七、速查表¶
7.1 数据结构对比¶
| 数据结构 | 查找 | 插入 | 删除 | 空间 | 适用场景 |
|---|---|---|---|---|---|
| 列表/数组 | O(n) | O(1)末尾 / O(n)中间 | O(n) | O(n) | 有序数据、按索引访问 |
| 字典/哈希表 | O(1) | O(1) | O(1) | O(n) | 键值映射、快速查找 |
| 集合 | O(1) | O(1) | O(1) | O(n) | 去重、成员判断 |
| 栈 | O(n) | O(1) | O(1) | O(n) | 后进先出场景 |
| 队列 | O(n) | O(1) | O(1) | O(n) | 先进先出场景 |
| 链表 | O(n) | O(1)头部 | O(1)已知位置 | O(n) | 频繁插入删除 |
| 二叉搜索树 | O(log n) | O(log n) | O(log n) | O(n) | 有序数据动态维护 |
| 图 | - | O(1) | O(1) | O(V+E) | 网络关系建模 |
注：哈希表的 O(1) 是平均情况，最坏可能退化为 O(n)
7.2 排序算法对比¶
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 特点 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 实际最快，但最坏情况差 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 时间稳定，适合链表排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 空间最省 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 最简单但最慢，仅供学习 |
| Python sorted() | O(n log n) | O(n log n) | O(n) | 稳定 | Timsort，实际开发直接用这个 |
稳定性：相等的元素排序后是否保持原来的相对顺序。生信中按多个字段排序时很重要。
7.3 算法复杂度速查¶
| 操作 | 时间复杂度 | 常见算法/场景 |
|---|---|---|
| 哈希表增删查 | O(1) | 字典操作、k-mer 计数 |
| 二分查找 | O(log n) | 有序数据查找、tabix |
| 单次遍历 | O(n) | 求和、计数、GC 含量 |
| 高效排序 | O(n log n) | 快排、归并、BAM 排序 |
| 两层循环 | O(n²) | 冒泡排序、简单比对 |
| DP 矩阵填表 | O(m*n) | 序列比对、编辑距离 |
| 子集枚举 | O(2ⁿ) | 特征选择暴力搜索 |
八、延伸资源¶
书籍¶
- 《算法图解》（Aditya Bhargava）：图文并茂，非常适合入门，Python 代码示例
- 《数据结构与算法 Python 语言实现》：系统学习用
在线课程¶
- LeetCode：刷题平台，从 Easy 开始刷，每天 1-2 题
- 力扣（中文版）：
leetcode.cn，题目有中文翻译 - Visualgo：
visualgo.net，算法可视化，看动画理解排序、搜索过程
生信相关¶
- Rosalind：
rosalind.info，用算法题学生物信息学，题目结合 DNA/蛋白质 - 《Bioinformatics Algorithms》（Compeau & Pevzner）：生信算法教材
刷题建议¶
- 先按类型刷：先把哈希表的题做 5 道，再做链表 5 道，不要随机跳
- 每道题做 3 遍：第一遍看思路写，第二遍独立写，第三遍优化
- 控制时间：Easy 20 分钟、Medium 40 分钟想不出来就看题解
- 重点刷：哈希表 > 双指针 > 二分查找 > 动态规划 > 树/图——这是面试频率排名
最后总结：算法不需要你从零发明，需要你认识问题类型 -> 选对数据结构和算法 -> 写出正确代码。生信面试不会考很难的算法题，但基础的哈希表、排序、二分查找、动态规划一定要会。每天刷 1-2 道 LeetCode，坚持两周就能应付大部分面试了。