Computational complexity of multiple sequence alignment with SP-score.
It is shown that the multiple alignment problem with SP-score is NP-hard for each scoring matrix in a broad class M that includes most scoring matrices actually used in biological applications. The problem remains NP-hard even if sequences can only be shifted relative to each other and no internal gaps are allowed. It is also shown that there is a scoring matrix M(0) such that the multiple alignment problem for M(0) is MAX-SNP-hard, regardless of whether or not internal gaps are allowed.
Just
W
W
Department of Mathematics, College of Arts & Sciences, Morton Hall 321, Ohio University, Athens, OH 45701, USA. just@math.ohiou.edu
D000465:Algorithms; D019295:Computational Biology; D015233:Models, Statistical; D016415:Sequence Alignment / Q000706:statistics & numerical data*