多重整列
大局的に最適な多重整列を求めるためには動的計画法を用いる。アミノ酸配列の場合は、ギャップペナルティと、あるアミノ酸から他のアミノ酸への置換の起こりやすさを示す置換行列をパラメータとして与える。核酸配列の場合にもギャップペナルティと置換行列を用いるが、置換行列は置換が起きるか否かのみを考慮した単純なものを使う場合が多い。
独立したn個の配列を整列するために、単純にはペアワイズアラインメントをn次元に拡張すれば良い。しかしnの増加に伴って計算量が指数的に増加し(配列の長さをLとしてO(L))、NP完全であることが示されている。
多重整列(たじゅうせいれつ、英: multiple sequence alignment)とは、DNAの塩基配列やタンパク質のアミノ酸配列について、3つ以上の配列間で対応する部分が並ぶように整列したもの、また整列すること。通常、整列する配列群は進化的類縁性を持っていることが仮定される。多重整列の結果に基づいて分子系統樹を推定することができる。