negative topology constraints

[Jacek Kominek]

Hi everybody, long time no see ;)

I'm currently doing some phylogenetic hypothesis testing, and while it's perfectly possible to enforce topological constraints in RAxML using -g and -r, I was wondering about forcing negative constraints i.e. preventing a specific topology from being present in the ML output? I know MrBayes has that particular feature, but it takes forever to run and is not really useable for anything larger that 100 taxa if you want to get good mixing and convergence, soooo.....

I couldn't find anything in the RAxML manual, and I only found one post from 4 years ago here in the group asking about this, with a negative answer at the time, did anything change? I assume that it did not, but I was wondering if there are any clever tricks that can be used with the positive constraints to simulate that, maybe? Such as taking each taxon and forcing it out of the monophyletic group, and then comparing likelihoods or doing topology tests (SH, AU etc.) against the monophyletic or unconstrained ML trees or something along these lines? Any ideas are welcome,

Cheers,

-Jacek

[Alexandros Stamatakis]

Dear Jacek,

We are currently working on a complete RAxML re-design, so we will
definitely not implement negative constraints in the current RAxML
version 8 code, but might do so later-on on the new RAxML code albeit
this is not on the high priority feature list.

I can't think of any simple trick for using positive constraints to
emulate negative constraints, but I will think about this a bit more.

Alexis

> --
> You received this message because you are subscribed to the Google
> Groups "raxml" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to raxml+un...@googlegroups.com
> <mailto:raxml+un...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout.

--
Alexandros (Alexis) Stamatakis

Research Group Leader, Heidelberg Institute for Theoretical Studies
Full Professor, Dept. of Informatics, Karlsruhe Institute of Technology
Adjunct Professor, Dept. of Ecology and Evolutionary Biology, University
of Arizona at Tucson

www.exelixis-lab.org

[Jacek Kominek]

Hi Alexis, thanks for the reply and clarification!

I'm glad to hear that a redesign is in the works, although RAxML is already pretty damn awesome ;)

As for the negative constraints, I understand that it's not a very burning question...I can also imagine that it's easier to implement in bayesian inference, since you are exploring the topology space pretty broadly already, and can constrain it at the run level or simply ignore the constrain-breaking steps. I imagine in a hill-climbing ML you're more oriented upwards and the algorith is also more likely to hit a likelihood terrace issue, since there are very many ways you could satisfy a negative constraint as opposed to a positive one. A crude solution I can think of would be to get a normal ML tree, then do some SPR/NNI/TBR to find a (heuristically) good alternative tree satisfying the negative constraint, then freeze the topology and optimize the branch lengths on it, but that by no means would guarantee anything. Still, just something to think about. Thanks again!

Best,

-Jacek

[Alexandros Stamatakis]

Dear Jacek,

Sorry for my long silence.

> I'm glad to hear that a redesign is in the works, although RAxML is
> already pretty damn awesome ;)

it's pretty crappy software, but don't tell anyone I said so ;-)

> As for the negative constraints, I understand that it's not a very
> burning question...I can also imagine that it's easier to implement in
> bayesian inference, since you are exploring the topology space pretty
> broadly already, and can constrain it at the run level or simply ignore
> the constrain-breaking steps.

Not so sure, after all either under ML or BI when you propose a new
topology you will have to check if it complies with the constraint ...

> I imagine in a hill-climbing ML you're
> more oriented upwards and the algorith is also more likely to hit a
> likelihood terrace issue,

I am not sure if a ML algorithm is more likely to hit a terrace, BI also
faces problems with this (see this paper:
http://sysbio.oxfordjournals.org/content/64/5/709) also you might
imagine that due to its nature BI once it is on a terrace might be
sampling trees from that terrace for far longer than a greedy ML
algorithm ....

> since there are very many ways you could
> satisfy a negative constraint as opposed to a positive one. A crude
> solution I can think of would be to get a normal ML tree, then do some
> SPR/NNI/TBR to find a (heuristically) good alternative tree satisfying
> the negative constraint, then freeze the topology and optimize the
> branch lengths on it, but that by no means would guarantee anything.
> Still, just something to think about. Thanks again!

Negative constraints are really a different animal implementation-wise,
as far as I remember Garli implements a negative constraint option.

Using postive constraints to circumvent negative constraints will not
work I think. Consider the following example with 6 Taxa A,B,...,F and
assume you don't want to have the bipartition ABC|DEF I don't think that
there is a way to come up with a single positive constraint tree that
will disallow the tree induced by ABC|DEF

Hope this helps,

Alexis

> > an email to raxml+un...@googlegroups.com <javascript:>
> > <mailto:raxml+un...@googlegroups.com <javascript:>>.

> > For more options, visit https://groups.google.com/d/optout

> <https://groups.google.com/d/optout>.

>
> --
> Alexandros (Alexis) Stamatakis
>
> Research Group Leader, Heidelberg Institute for Theoretical Studies
> Full Professor, Dept. of Informatics, Karlsruhe Institute of Technology
> Adjunct Professor, Dept. of Ecology and Evolutionary Biology,
> University
> of Arizona at Tucson
>

> www.exelixis-lab.org <http://www.exelixis-lab.org>