building a cladogram with 100,000 sequences...

[brachysclereid]

Are there any tools capable of performing multi sequence alignment and tree construction that can handle up to 100,000 sequences?

[mbblack]

Are there any tools capable of performing multi sequence alignment and tree construction that can handle up to 100,000 sequences?

That many sequences is still pretty much in the intractable range, to my knowledge. There are tools that reportedly do alright with up to 10,000 sequences (although most of the ones I know of - SATCHMO, MUMMALS, etc) are designed for protein sequences, although MAFFT will handle protein or DNA.

In order to do what you are asking, you really should cluster the sequences first, then align from smaller sets.

MUSCLE's manual recommends using the UCLUST tool in USEARCH (http://www.drive5.com/usearch/) to reduce the number of alignments needed. And if you contact MUSCLE's author (http://www.drive5.com/muscle/about.htm) he mentions that he is working on something to leverage MUSCLE and USEARCH to deal with huge numbers of sequence alignments (without overly sacrificing accuracy).

[koadman]

Are your sequences all from the same locus, e.g. amplicon sequenced? If so, the usual approach to build a phylogeny involves first taking a representative subset, say 500 sequences, and building a profile HMM using HMMer3 or building a SCFG using Infernal if the sequences are RNA with known secondary structure. With your HMM or SCFG in hand you can then quickly construct a multiple alignment of all 100k of them. see hmmalign. You can then feed the alignment to Morgan Price's FastTree or one of the other programs that can construct a phylogeny in subquadratic time.

That approach works well if you care only about substitutions in the evolutionary history (this is what most people want since they usually hold the richest evolutionary signal). If you care about indel histories you will have to do a full multiple sequence alignment with something like MUSCLE, MAFFT or another tool. I am not aware of any indel history inference tools that can operate on such large datasets. Maybe someone else knows of such methods?

[colindaven]

Can you take a subset by looking at clusters ? Some good software for this purpose is RAMMCAP.

[ssing]

RAxML should be able to handle that many tips, but it cannot align... GARLI is also efficient at making large trees from alignments, but I don't know what its upper limit is.

[brachysclereid]

building a cladogram with 100,000 sequences

Thanks for all the advice. It will take a while to sort through all the possibilities. Perhaps clustering first will be a good approach.

I'll make a post if I can get something to work. In the mean time other suggestions would be greatly appreciated!