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].

The complexity of multiple sequence alignment with SP-score that is a metric

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA
2001

Abstract

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.
Articolo in rivista - Articolo scientifico
multiple sequence alignment; SP-score; intractability
English
63
79
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].
Bonizzoni, P; DELLA VEDOVA, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/1282
Citazioni
  • Scopus 83
  • ???jsp.display-item.citation.isi??? 73
Social impact