Multiple Sequence Alignment as a Facility-Location Problem
Winfried Just, Gianluca Della Vedova · INFORMS journal on computing · 2004
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.