This paper analyzes the computational complexity of computing the optimal alignment of a set of sequences under the sum of all pairs (SP) score scheme. We solve an open question by showing that the problem is NP-complete in the very restricted case in which the sequences are over a binary alphabet and the score is a metric. This result establishes the intractability of multiple sequence alignment under a score function of mathematical interest, which has indeed received much attention in biological sequence comparison. (C) 2001 Elsevier Science B.V. All rights reserved.
Bonizzoni, P., & Della Vedova, G. (2001). The complexity of multiple sequence alignment with SP-score that is a metric. THEORETICAL COMPUTER SCIENCE, 259(01-feb), 63-79 [10.1016/S0304-3975(99)00324-2].
Citazione: | Bonizzoni, P., & Della Vedova, G. (2001). The complexity of multiple sequence alignment with SP-score that is a metric. THEORETICAL COMPUTER SCIENCE, 259(01-feb), 63-79 [10.1016/S0304-3975(99)00324-2]. | |
Tipo: | Articolo in rivista - Articolo scientifico | |
Carattere della pubblicazione: | Scientifica | |
Titolo: | The complexity of multiple sequence alignment with SP-score that is a metric | |
Autori: | Bonizzoni, P; Della Vedova, G | |
Autori: | ||
Data di pubblicazione: | 28-mag-2001 | |
Lingua: | English | |
Rivista: | THEORETICAL COMPUTER SCIENCE | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/S0304-3975(99)00324-2 | |
Appare nelle tipologie: | 01 - Articolo su rivista |