main page

    Settling the Intractability of Multiple Alignment

    Isaac Elias

    Abstract

    In this paper some of the most fundamental problems in computational biology are proved intractable. The following problems are shown NP-hard for all binary or larger alphabets under all fixed metrics: Multiple Alignment with SP-score, Star Alignment, and Tree Alignment (for a given phylogeny). Earlier these problems have only been shown intractable for sporadic alphabets and distances, here the intractability is settled. Moreover, the construction can be extended to prove NP-hardness results for Consensus Patterns and Substring Parsimony.

    Download

    Journal of Computational Biology, volume 13, number 7, pages 1323-1339, Sep 2006.
    (Link to JCB)

    In Proc. of the 14th Ann. Int. Symp. on Algorithms and Computation (ISAAC'03), volume 2906 of Lecture Notes in Computer Science, pages 352-363. Springer-Verlag, November 2003.
    (PDF, Springer)

    Technical Report TRITA-NA-0316, Nada, KTH, 2003.
    (PS, PDF)

    Slides from presentation given at Tel-Aviv University, Israel 2004
    (PDF)

    Google scholar citations Go Citeseer

    BibTex 

    @Article{Elias:MSA_NPHARD,
  author =      {I. Elias},
  title =       {Settling the Intractability of Multiple Alignment},
  journal =     {Journal of Computational Biology},
  year =        {2006},
  pages =	{1323--1339},
  volume =	{13},
  month =	{September},
  number =      {7}
}

@InProceedings{ISAAC03:Elias,
  author =      {Isaac Elias},
  title =	{Settling the Intractability of Multiple Alignment},
  booktitle =	{Proc. of the 14th Ann. Int. Symp. on Algorithms and 
                Computation ({ISAAC}'03)},
  pages =	{352--363},
  year =	{2003},
  volume =	{2906},
  series =	{Lecture Notes in Computer Science},
  month =	{November},
  publisher =	{Springer-Verlag},
  ISBN =	{0302-9743},
}

@TechReport{REPORT03:Elias,
  author =      {Isaac Elias},
  title =	{Settling the Intractability of Multiple Alignment},
  year =	{2003},
  number =	{TRITA-NA-0316},
  institution =	{Nada, KTH},
}