IRIS – Institutional Research Information System
IRIS è il sistema di gestione della ricerca dell’Università degli Studi di Milano-Bicocca.Il repository BOA è il modulo del sistema dedicato alla raccolta e alla disseminazione della produzione scientifica di Ateneo. Le pubblicazioni sono ricercabili per parola chiave attraverso il box nella barra orizzontale in alto oppure, mediante il pulsante Sfoglia, per "Afferenza", "Autore", "Titolo", "Tipologia" o "Settore scientifico-disciplinare".
IRIS contiene inoltre alcuni moduli dedicati alla registrazione dei progetti e dei contratti, e alla reportistica avanzata per le attività di valutazione della ricerca
EnglishThis 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.
Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/10281/1282| 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. |
| 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 interni: | BONIZZONI, PAOLA DELLA VEDOVA, GIANLUCA |
| Data di pubblicazione: | 28-mag-2001 |
| Lingua: | English |
| Rivista: | THEORETICAL COMPUTER SCIENCE |
| Appare nelle tipologie: | 01 - Articolo su rivista |
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.
Copyright © 2017