@InProceedings{Waldispuehl:etal:TMBalign:RECOMB09,
  author =	 {J{\'e}r{\^o}me Waldisp{\"u}hl and Charles
                  W. O'Donnell and Sebastian Will and Srinivas Devadas
                  and Rolf Backofen and Bonnie Berger},
  title =	 {Simultaneous Alignment and Folding of Protein
                  Sequences},
  booktitle =	 RECOMB09,
  user =	 {will},
  editor =	 {Serafim Batzoglou},
  publisher =	 {Springer},
  location =	 {Heidelberg},
  series =	 {LNBI},
  volume =	 5541,
  year =	 2009,
  isbn =	 {978-3-642-02007-0},
  pages =	 {339--355},
  abstract =	 {One of the central challenges in computational
                  biology is to develop accurate tools for protein
                  structure analysis. Particularly difficult cases of
                  this are sequence alignment and consensus folding of
                  low-homology proteins. In this work, we present
                  partiFold-Align, the first algorithm for
                  simultaneous alignment and consensus folding of
                  unaligned protein sequences; the algorithm's
                  complexity is polynomial in time and
                  space. Algorithmically, partiFold-Align additionally
                  exploits sparsity in the set of likely
                  super-secondary structure pairings and alignment
                  candidates for each amino acid to achieve an
                  effectively cubic running time for simultaneous
                  pairwise alignment and folding. We demonstrate the
                  efficacy of these techniques on transmembrane
                  beta-barrel proteins, an important yet difficult
                  class of proteins with very few available
                  three-dimensional structures. In tests on sequence
                  alignments derived from structure alignments,
                  partiFold-Align is significantly more accurate than
                  current best approaches for pairwise sequence
                  alignment in the difficult case of low sequence
                  homology and improves secondary structure prediction
                  when current approaches fail. Importantly,
                  partiFold-Align does not require training on
                  transmembrane beta-barrel proteins. The generality
                  of these techniques should allow them to be applied
                  to a wide variety of protein structures.}
}