Sequence Alignment 序列对齐
Sequence Alignment 这个话题在 Wikipedia 上用于研究 DNA, RNA 序列片段的对齐问题。
- Bioinformatics - methods and software for understanding biological data
- Sequence Alignment
- global alignment
- Local Alignment
序列对齐
基因序列对齐的示例
G T T - A C
| | | | |
G T T G A C
Smith–Waterman algorithm
有点类似与 Longest Common Subsequence 算法。
相对 LCS 来说，序列中的元素时有限的。即使是相同的字符，位置距离过远时，不能认为是 common。
所以用词上强调 match ，而不是 common.
实现上类似于 Levenshtein Distance，动态规划计算 cost 值。