Genome-scale multiple sequence alignments are not quite good for phylogenies: they take a lot of time to compute and are never accurate. Moreover, it's hard to imagine a general-purpose sequence evolution model that would be equally adequate for protein-coding, rRNA, tRNA genes, repeats and other regions. Picking a subset of genes manually is not a nice option either, because you will lose a lot of phylogenetic resolution. I would thus recommend building a tree based on all orthologous genes, which is the most common thing to do as far as I can tell. Here is a general pipeline:

1. Annotate your genomes using Prokka (for prokaryotes) or another tool;
2. Find one-to-one protein-coding orthologs using OrthoFinder or OrthoMCL;
3. Run multiple sequence alignments (MSAs) for each group (any MSA tools will do, but I prefer mafft);
4. Filter each MSA using Gblocks;
5. Merge filtered alignments (I use Python for that, but I'm pretty sure there are some tools that don't require programming skills);
6. Use raxml (maximum likelihood) or beast (bayesian inference) to infer the phylogeny.

RaxML: I'm not sure but I think this program works for entire genomes and is supposed to be very fast:

Results: In this paper we present the latest release of our program RAxML-III for rapid maximum likelihood-based inference of large evolutionary trees which allows for computation of 1.000-taxon trees in less than 24 hours on a single PC processor. We compare RAxML-III to the currently fastest implementations for maximum likelihood and bayesian inference: PHYML and MrBayes. Whereas RAxML-III performs worse than PHYML and MrBayes on synthetic data it clearly outperforms both programs on all real data alignments used in terms of speed and final likelihood values.

Alignment of whole genomes is a quite delicate task and a pain to parse a lot of different output formats until a measure of distance/similarity emerges. Good aligners are MUMMER and MAUVE. I really like MAUVE, used it to play with a lot of genomes from different strains of E. coli. That's the advantage of whole genome comparision! You can find "species" tree even when 16S says that the distance is zero.

For the phylogeny part of the work, you can use RaxML as said by some folks here. For high number of taxa this guy is the fastest one on the road. In your case a more precise approach is feasible. So, you can use ERATE which is Sean Eddy's version of DNAML from Phylip. It can deal with indels and I recommend it even in the 16S case.

But, if you really don't wanna suffer, just check the Genome-To-Genome Distance Calculator service and choose your own setup. After getting the distances, just use Clearcut to generate a NJ tree. Fast and cheap! Not very accurate if you work with very divergent species.

Hi, the approach at MicrobesOnline looks interesting. If the 24 species genomes are public and high quality their phylogenetic positions may already be there for you (click on "Species Tree"). If they are unpublished genomes they also allow you to host data privately- although I am only assuming that you would then be able to add them to the existing data sets, I don't know for sure.

The trees are made from 78 protein coding loci, so not "whole genomes" but the difference is probably trivial for most species.

Which program would be a more modern and better alternative to Phylip PARS for clustering 0/1 data representing presence/absence of genes amongst multiple strains of bacteria?

It's a very old post but I thought I could add to it to help others who might want to do a similar analysis i.e. create phylogenies from whole genomes for prokaryotic species. I have created a basic analysis pipeline that tries to simplify the process of creating phylogenetic trees at species level using only the conserved (otherwise known as the core) genomic content of all the 'bacterial' species. The steps used are described and the script is available at http://mcgp.sourceforge.net/

This tool may work.

https://realphy.unibas.ch/fcgi/realphy

PHYLIP

Edit (seeing that I had neglected the 'whole genome'): phylip tools could also be used for creating a phylogeny, in addition or as an alternative to tools mentioned by Lars, either on single genes or a mixture of genes from the genome. eg:

• dnapars (parsimony based reconstruction of phylogeny )
• dnaml (maximum likelihood based)
• neighbor can compute trees from a distance matrix by neighbor joining or UPGMA
• drawgram and drawtree can help to draw rooted or unrooted trees in newick format
• consense can make a consensus tree from multiple trees, in case you try combine different markers

There are possibly better solutions for each task listed out there.

Edit: (because some dislike this set of tools for some possibly good reason) They are also maintaining a large list of other phylogeny software

I admit, it wouldn't be easy for me to choose from this list, so I would again tend to try the tools in the EMBOSS package first, which are mostly re-implementations of the phylip tools.

And of course I would appreciate if people would care also to provide some arguments for their preference of one method over the other, not just "don't use ... because it's bad (in 20 years)".

If by whole genome you mean you want to include intrinsic genome sequence features there might be oligo-nucleotide frequencies, gc content, codon-usage, out of which a distance matrix can be contructed which again could be clustered using neighbor joining. This tree might be very different from the ones you get by 16S analysis.

The VCF2PopTree software would be helpful if you are constructing a phylogenetic tree from VCF or SNP file. It reads even the human genome. It is so cool and it does not need any dependencies.

The software link is as follows: http://sankarsubramanian.net/dat/index.html