Minimum Spanning Tree

Question

[Lee Katz]

Hi all, I am just wondering, given a multiple sequence alignment, what is your favorite way to draw a minimum spanning tree?

[jingtao09]

Not sure why it relates to the MST. but if you want to draw a phylogeny tree, then here is my idea:

---

1.

compute the N by N matrix with similarity or edit distance score from any algo.

2.

using "neighbor join"

algorithm to compute the matrix. (PHYLIP,etc.)

3.

take step 2's result to draw the phylogenetic tree (TreeView X)

4.

good luck!

Answer 1

[Josh Herr]

I'm unclear about what you mean by "minimal spanning tree", I assume you are referring to a phylogenetic tree with the shortest total branch length?

I'm also not sure what you mean by "way to draw": I personally have used PAUP, PHYLIP, Phyml, RAxML, BEAST, and Mr. Bayes to estimate trees over the past few years. I think FigTree is great for phylogenetic tree visualization. I'm not a very big fan of MEGA because of its awkwardness and file conversion issues, but that's my personal take on older versions of MEGA.

It really matters which model you choose when you are estimating a phylogenetic tree to find the shortest total branch length. First off, depending on what type of data you have, the quality of your matrix or alignment and how you define homologous and non-homologous characters in your sequence alignment can drastically affect your branch lengths. The number of state changes per site across your alignment translates to your branch length, so the economy of your sequence data is key. In other words, SNP data can give you short branch lengths versus some other more variable sequence data which would provide longer branch lengths.

For a quick tree, you can use a distance algorithm (UPGMA or Neighbor Joining) or choose a substitution model (Maximum Likelihood), and if you've got more time on your hands, choose more exhaustive Maximum Parsimony or Bayesian analysis. All of these methods 'should' progressively provide you with shorter branch lengths during your phylogenetic analysis. This protocol, Choosing a Method for Phylogenetic Prediction, ignores Bayesian analysis but otherwise is a good place to start to decide which model to use to analyze your sequence data.