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 [10.1287/ijoc.1040.0093].
Multiple sequence alignment as a facility location problem
DELLA VEDOVA, GIANLUCA
2004
Abstract
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
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.
