The Prague Stringology Club Workshop 2000
Winfried Just and Gianluca Della Vedova
Multiple Sequence Alignment as a Facility Location Problem
| 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. |
| Download paper: |  |
 |
| PostScript |