Aritalab:Lecture/Bioinformatics/Alignment

Needleman-Wunsch アルゴリズム

1970年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまではNeedleman-Wunsch アルゴリズムと呼ばれています。

基本はLCSアルゴリズムと同じですが、ギャップとミスマッチに対してそれぞれペナルティスコアが与えられています。

$s_{i,j} = max \begin{cases} s_{i-1,j} - \sigma \\ s_{i,j-1} - \sigma \\ s_{i-1,j-1} - \mu & \mbox{if } x \ne y \\ s_{i-1,j-1} +1 & \mbox{if } x = y \end{cases}$

具体的なアルゴリズムとJavaコードはこちらを参照してください。