A connection is made between certain multiple-sequence alignment problems and facility-location problems, and the existence of a PTAS (polynomial-time approximation scheme) for these problems is shown. Moreover, it is shown that multiple sequence alignment with SP-score and fixed gap penalties is MAX SNP-hard
Just, W., & Della Vedova, G. (2004). Multiple sequence alignment as a facility location problem. INFORMS JOURNAL ON COMPUTING, 16(4), 430-440.
Citazione: | Just, W., & Della Vedova, G. (2004). Multiple sequence alignment as a facility location problem. INFORMS JOURNAL ON COMPUTING, 16(4), 430-440. |
Tipo: | Articolo in rivista - Articolo scientifico |
Carattere della pubblicazione: | Scientifica |
Titolo: | Multiple sequence alignment as a facility location problem |
Autori: | Just, W; Della Vedova, G |
Autori: | |
Data di pubblicazione: | 2004 |
Lingua: | English |
Rivista: | INFORMS JOURNAL ON COMPUTING |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1287/ijoc.1040.0093 |
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.