-
Notifications
You must be signed in to change notification settings - Fork 0
HOWTO:Trees
This page is under construction.
This HOWTO is translated from BioPerl HOWTO:Trees. The original document is copyright Jason Stajich. It can be copied and distributed under the terms of the Perl Artistic License.
Jason Stajich, Dept. Molecular Genetics and Microbiology, Institute for Genome Sciences and Policy, Duke University. <jason-at-bioperl.org>
This document is copyright Jason Stajich. It can be copied and distributed under the terms of the Perl Artistic License.
|---|---| |Revision 0.1 2003-12-01 JES|First version| |Revision 0.2 2004-11-05 BIO|Add SVG section and links| |Revision 0.3 2005-07-11 JES|Explore Node objects more| |Revision 0.4 Torst 05:49, 22 December 2005 (EST)|Wiki version|
This HOWTO intends to show how to use the BioRuby Tree objects to manipulate phylogenetic trees. It shows how to read and write trees, query them for information about specific nodes or overall statistics, and create pictures of trees. Advanced topics include discussion of generating random trees and extensions of the basic structure for integration with other modules in BioRuby.
Generating and manipulating phylogenetic trees is an important part of modern systematics and molecular evolution research. The construction of trees is the subject of a rich literature and active research. This HOWTO and the modules described within are focused on querying and manipulating trees once they have been created.
The data we intend to capture with these objects concerns the notion of Trees and their Nodes. A Tree is made up of Nodes and the relationships which connect these nodes. The basic representation of parent and child nodes is intended to represent the directionality of evolution. This is to capture the idea that some ancestral species gave rise, through speciation events, to a number of child species. The data in the trees need not be a strictly bifurcating tree (or binary trees to the computer science types), and a parent node can give rise to 1 or many child nodes.
In practice there are just a few main objects, or modules, you need to know about. There is the main Tree object Bio::Tree which is the main entry point to the data represented by a tree. A Node is represented generically by Bio::Tree::Node, however there would be subclasses of this object to handle particular cases where we need a richer object. The connections between Nodes are described by using Bio::Tree::Edge. Unlike BioPerl, Nodes do not have any pointers or references. An Edge object has just two pointers to Nodes to be connected. The two Nodes are equally treated, and no parents-children relationships are recorded in the Edge objects. Unlike BioPerl, data specific to nodes, like bootstrap values and labels, are stored in the Node objects, and data specific to edges, like distances, are stored in the Edge objects. The Bio::Tree object is just a container for some summary information about the tree, nodes and edges in the tree, and a description of the tree's root node.
Trees are used to represent the ancestry of a collection of taxa, sequences, or populations.
Using Bio::FlatFile one can read trees from files or datastreams and create Bio::Tree objects. This is analogous to how we read sequences from sequence files with Bio::FlatFile to create BioRuby sequence objects which can be queried and manipulated. Similarly we can write Bio::Tree objects out to string representations like the Newick or New Hampshire tree formats which can be printed to a file, a datastream, stored in database, etc.
The main module for reading and writing trees is the Bio::FlatFile factory class which calls several driver classes. These drivers include Bio::Newick for New Hampshire or Newick tree format, and for the New Hampshire extended tree format from Sean Eddy and Christian Zmasek as part of their RIO, Forrester and ATV system RIO,ATV,SDI. The parser Bio::Nexus supports parsing tree data from PAUP's Nexus format. However this driver currently only supports parsing, not writing, of Nexus tree format tree files. There are also modules for lintree tree format and Pagel tree format for writing these formats out. The phyloxml tree format will be supported in the future.
By default, Bio::Newick automatically determines whether the internal nodes id encode bootstrap values instead of IDs or not. If you do not like the default behavior, giving appropriate :bootstrap_style option to Bio::Newick.new. This is only valid for the Nexus and Newick tree formats.
Here is some code which will read in a Tree from a file called "tree.tre" and produce a Bio::Tree object which is stored in the variable tree.
Like most modules which do input/output you can also specify an IO object instead of the filename.
require "bio"
# parse in newick/new hampshire format
input = Bio::FlatFile.open(Bio::Newick, "tree.tre")
tree = input.next_entry.tree
Once you have a Tree object you can do a number of things with it. These are all methods required in Bio::Tree.
For example try these two difference example scripts that read in a tree data and prints out the the node ids and bootstrap values. The first example assumes that internal node ids are Ids and not bootstrap values.
require "bio"
treeio = Bio::FlatFile.open(Bio::Newick, DATA)
while newick = treeio.next_entry
newick.options[:bootstrap_style] = :disabled
tree = newick.tree
#tree.reparse
tree.each_node do |node|
printf "id: %s bootstrap: %s\n", node.name || '', node.bootstrap || ''
end
end
__END__
(((A:5,B:5)90:2,C:4)25:3,D:10);
The second is just the default behavior that Bio::Newick parser automatically moves the bootstrap values over from the internal node Ids.
require "bio"
treeio = Bio::FlatFile.open(Bio::Newick, DATA)
while newick = treeio.next_entry
tree = newick.tree
tree.each_node do |node|
printf "id: %s bootstrap: %s\n", node.name || '', node.bootstrap || ''
end
end
__END__
(((A:5,B:5)90:2,C:4)25:3,D:10);
One can also explictly invoke this by calling just calling the move_id_to_bootstrap method on a tree.
Request the taxa (leaves of the tree).
taxa = tree.leaves
Get the root node.
root = tree.root
Get the total length of the tree (sum of all the branch lengths), which is only useful if the edges (connections between nodes) actually have the branch length stored, of course.
total_length = tree.total_distance
Bio::Tree has many functions which are useful for manipulating a Tree.
Find a particular node, either by name or by some other field that is stored in a Node.
# find all the nodes named 'node1' (there should be only one)
nodes = tree.nodes.find_all { |x| x.name == 'node1' }
## find all the nodes which have description 'BMP'
# (???currently not available in BioRuby???)
#(perl) my @nodes = $tree->find_node(-description => 'BMP');
#nodes = tree.nodes.find_all { |x| x.name == 'BMP' }
# find all the nodes with bootstrap value of 70
nodes = tree.nodes.find_all { |x| x.bootstrap == 70 }
If you would like to do more sophisticated searches, like "find all the nodes with bootstrap values better than 70", you can easily implement this yourself.
# Be careful that bootstrap value can be nil.
nodes = tree.nodes.find_all { |x| x.bootstrap and x.bootstrap > 70 }
Remove a Node from the Tree and update the graph (children/ancestor links) where the Node is an intervening one.
# provide the node object to remove from the Tree
tree.remove_node(node)
# or specify the node Name to remove
# (be careful that all nodes named 'Node12' are removed)
tree.remove_node_if { |x| x.name == 'Node12' }
Get the lowest common ancestor for a set of Nodes. This method is used to find an internal Node of the Tree which can be traced, through its children, to the requested set of Nodes. It is used in the calculations of monophyly and paraphyly and in determining the distance between two nodes.
# Provide a list of Nodes (strictly, they <del>don't</del> have to be in this tree)
lca = nodes.inject { |x,y| tree.lowest_common_ancestor(x, y) }
The above works for 2 or more nodes. For just 2 nodes,
lca = tree.lowest_common_ancestor(node1, node2)
Get the distance between two nodes by adding up the branch lengths of all the connecting edges between two nodes.
distances = tree.distance(node1, node2)
Perform a test of Wp:monophyly for a set of nodes and a given outgroup node. This means the common ancestor for the members of the internal_nodes group is more recent than the common ancestor that any of them share with the outgroup node.
(coming soon)
Perform a test of Wp:paraphyly for a set of nodes and a given outgroup node. This means that a common ancestor 'A' for the members of the ingroup is more recent than a common ancestor 'B' that they share with the outgroup node and that there are no other nodes in the tree which have 'A' as a common ancestor before 'B'.
(coming soon)
Re-root a tree, specifying a different node as the root (and a different node as the outgroup).
# node can either be a Leaf node
# or it can be an internal node which will become the new
# root of the Tree
tree.root = node
(below is still under translation)