Alignment programs

Sean Eddy eddy at wol.wustl.edu
Fri Dec 22 10:43:01 EST 1995


In article <9512211406.AA01637 at faust.cc.duq.edu> garey at next.duq.edu ("Jim Garey") writes:
  >This is in reply to secondary structure based alignments of 18S rRNA:
  >When I began trying to find out how alignments could be done to "take
  >secondary structures into account" I encountered a lot of hand waving
  >(I mean a LOT of hand waving) and finally realized that most people
  >either use the RDP alignments or adjust alignments by eye using some
  >kind of sequence editor. 

For what it's worth, here are some (partially self-serving) references
to automatic RNA alignment algorithms that use both secondary
structure and primary sequence consensus information. The software for
these is available from me (ftp://genome.wustl.edu/pub/eddy) and from
David Haussler's group at Santa Cruz (ftp://ftp.cse.ucsc.edu/pub/rna).

They are still very much fledgling applications that aren't quite
ready to leave the theoretical nest, but they do demonstrate that
there's a clean, no-hand-waving, maximum likelihood solution to the
RNA secondary structure alignment problem. Both research groups are
taking advantage of models called "stochastic context-free grammars"
which have been used previously in speech recognition applications.

An important practical limitation is that the alignment algorithms are
extremely memory-intensive, and 18S or 28S rRNA are well beyond their
current capabilities on reasonable sized machines. 100-200 nt domains
are doable. "We're working on it." Leslie Grate in Haussler's group
has made some good progress on SCFG alignment algorithms that can deal
with rRNA.

@Article{Haussler94,
  author =       "David Haussler and Yasubumi Sakakibara and Michael Brown",
  title =        "Stochastic Context-Free Grammars for {tRNA} Modeling",
  journal =      NAR,
  year =         1994,
  volume =       22,
  pages =        "5112-5120"
}

@Article{Eddy94,
  author =       "Sean R. Eddy and Richard Durbin",
  title =        "{RNA} Sequence Analysis Using Covariance Models",
  journal =      NAR,
  year =         1994,
  volume =       22,
  pages =        "2079-2088"
}

--
- Sean Eddy
- Dept. of Genetics, Washington University School of Medicine
- eddy at genetics.wustl.edu




More information about the Mol-evol mailing list