[Dart-announce] Phylo-grammars... MCMC alignment... Brazil, Benasque and Booze...

[Ian H. <ih...@bd...>]

....DART news.... ....Berkeley.... ....September 2005....
(Scroll down for the DART website at the foot of this email.)

Hello there, fellow evolutionary hackers, RNA tinkerers and
phylo-enthusiasts! This is the latest missive on dart-announce, the
low-volume mailing list describing developments with the DART package,
your FAVOURITE software for evolutionary bioinformatics... er, OK, my
British upbringing demands more disclaimers in that sentence. How about:
your favourite software for FAST evolutionary bioinformatics... counting
only open source programs WRITTEN IN C++...... in Berkeley........ by me.
yeah, that shouldn't offend anyone. (WE RULE!!!!) (*ahem*)

If nothing else, dart SURELY must be your favourite GPL'd software that
comes with an opportunity to SCORE some FREE BOOZE[*]! (Let's see if that
makes it past the spam filters.) That's right:-- the 2004 bug hunt,
despite being prolonged well into 2005, has finally reached its inevitable
conclusion. Carolin Kosiol, working with Nick Goldman's group, found some
cool sparse data glitches while experimenting with "xrate" on 61-state
codon models. Yes, that means rate matrices with an almighty 61*61
parameters! (Give or take a factor of 2 due to reversibility constraints.)

Hopefully the problems disclosed by Carolin et al have now been fixed:
both in the sense that we have patched the code (adding pseudocounts and
various checks for robustness), and in the sense that we have effectively
SILENCED Carolin and crew by sending them a crate of 12 bottles of some of
the finest wines produced in my old stomping ground, the Yarra valley in
Victoria, Australia. (Remember that old Monty Python sketch about
Australian wines: "they really open up the sluice-gates at both ends".) So
that should be the last we hear from Carolin and Nick for a while (well,
that's the theory anyway). Anyone else who reckons they're hard enough,
come and have a go! Best bug found by summer 2005 wins the discoverer a
similarly punishing alcoholic stupor.

(A shout out is due to Sam Griffiths-Jones and Alex Bateman, of RFAM, who
came a close second with their heavy-duty testing of the StemLoc program;
much valuable feedback, thanks guys. Maybe next year the booze will be
yours...)

[*] I believe that Ewan Birney has stopped doling out champagne as a bug
prize for his GeneWise programs, though I'm prepared to be corrected.
Ewan?

BTW, lest it escape anyone's attention, the point of doing this kind of
bughunting prize (aka "pandering to beta testers") is that, as a result,
we have VERY FEW BUGS. For example: to my knowledge, dart programs never
segfault. Ever. Some of the more bloated RNA alignment algorithms have
been known to abort when they run out of memory, but that's par for the
course. Dart is _very_ robust software and we intend to keep it that way
(and bribe off any dissenters with fine wines, muahahahaa).

Moving on: XRate, the abovementioned software for estimating
instantaneous rate matrices, continues to be our most popular tool (but
closely followed by StemLoc; see below). This year, Pete Klosterman has
worked to adapt XRate to estimate *irreversible* rate matrices, using a
generalisation of the eigenspace-EM algorithm that powers the reversible
version. (Much credit should also go to Gerton Lunter, Robert Davies and
others who were kind enough to contribute asymmetric linear algebra
codes.)

XRate has also been adapted to incorporate arbitrary stochastic grammars
(including algorithms like Thorne-Goldman-Jones for predicting secondary
structure of proteins, and Knudsen-Hein for that of RNA). We have also
implemented the basic Siepel-Haussler technique for context-sensitive
substitutions (e.g. incorporating CpG effects, or basepair stacking in
RNA; irreversibility can be an important consideration in this sort of
model). As a result, we now have spin-off programs for working with
evolutionary or "phylo"-HMMs/SCFGs (XFold/XProt, for RNA/protein,
respectively).

XRate (and its spinoffs XFold and XProt) have been applied in a number
of "big genomics" projects this year, including ENCODE and analysis of
the 12 fruitfly genomes. We hope to expand this.

In other developments, the Handel program (MCMC sampling of multiple
sequence alignments) can now be used together with elaborate
phylo-grammar programs (like XFold and XProt) to sample from the
likelihood function of such phylo-grammars, using a Metropolis-like
accept/reject scheme. That is, you can pipe the sampled alignments from
Handel directly into XFold, and thereby explore XFold's alignment space
using the Handel sampling engine. We're still testing this capability
but expect it to be very powerful. As always, you can download the code
from SourceForge (advance warning: we may move the CVS repository to our
own machines in the near future; anonymous CVS access will still be
offered).

Our RNA-oriented tools are also still going strong. Development continues
on "evoldoer" (our RNA evolutionary aligner) and "StemLoc" (for RNA
multiple alignment). Our current favoured way to proceed with RNA multiple
alignment is an MCMC-type approach. We're about to invest in a machine
with 32GB of RAM (currently we're limited to 8GB) specifically so we can
play around with some of these high-memory RNA algorithms. Keep watching
this space.

Anyway, enough rambling from me. Keep hacking away. See you all at
ISMB in Brazil, or Benasque'06, or some such cool compbio venue.

Ian Holmes, ihh at berkeley dot edu
UC Berkeley, Dept of Bioengineering
September 7, 2005

DART website: http://biowiki.org/dart