Multiple Sequence Alignment as a Facility-Location Problem
Winfried Just, Gianluca Della Vedova
INFORMS Journal on Computing · 2004 · Volume 16 · Issue 4
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.
Keywords
analysis of algorithms: computational complexity, facilities-equipment planning: location
Enable JavaScript for citation tools and additional paper interactions.