The Prague Stringology Club Workshop 2000

Winfried Just and Gianluca Della Vedova

Multiple Sequence Alignment as a Facility Location Problem

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.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF