title: Computational complexity of multiple sequence alignment with SP-score.
abstract: 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.
authors.affiliation: Department of Mathematics, College of Arts & Sciences, Morton Hall 321, Ohio University, Athens, OH 45701, USA. just@math.ohiou.edu
authors.forename: W
authors.initials: W
authors.lastname: Just
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D015233:Models, Statistical; D016415:Sequence Alignment / Q000706:statistics & numerical data*