<!DOCTYPE article  PUBLIC "-//OASIS//DTD DocBook V4.1//EN">
  <article lang="en">
    <articleinfo>
      <title>Phylogenetic Tree HOWTO</title>
      <author>
	<firstname>Jason</firstname>
	<surname>Stajich</surname>
	<authorblurb>
	  <para>Bioperl Core Developer</para>
	</authorblurb>
	<affiliation>
	  <orgname>Dept Molecular Genetics and Microbiology,
	  Duke University</orgname>
	  <address><email>jason AT bioperl.org</email></address>
	</affiliation>
      </author>

      <pubdate>2003-12-01</pubdate>
      <revhistory>
	<revision>
		<revnumber>0.1</revnumber>
		<date>2003-12-01</date>
		<authorinitials>JES</authorinitials>
		<revremark>First version</revremark>
	</revision>
       </revhistory>
      <legalnotice>	
	<para>This document is copyright Jason Stajich, 2003.  It can
        be copied and distributed under the terms of the Perl
        Artistic License.
	</para>
      </legalnotice>

    <abstract>
      <para>
	This HOWTO intends to show how to use the Bioperl Tree objects to
	manipulate phylogenetic trees.  It shows how to read and write
	trees, query them for information about specific nodes or
	overall statistics.  Advanced topics include discussion of
	generating random trees and extensions of the basic structure
	for integration with other modules in Bioperl.
      </para>
    </abstract>
  </articleinfo>

  <section id="introduction">
    <title>Introduction</title>
    <para>
      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.      
      </para>

      <para>
      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
      CS types), and a parent node can give rise to 1 or many child
      nodes.  
      </para> 
      <para>

      In practice there are just a few main
      objects, or modules, you need to know about.  There is the main
      Tree object <emphasis>Bio::Tree::Tree</emphasis> which is the main
      entry point to the data represented by a tree.  A Node is
      represented generically by <emphasis>Bio::Tree::Node</emphasis>,
      however there are subclasses of this object to handle particular
      cases where we need a richer object (see
      <emphasis>Bio::PopGen::Simulations::Coalescent</emphasis> and
      the PopGen HOWTO for more information).  The connections between
      Nodes are described using a few simple concepts. There is the concept of
      pointers or references where a particular Node keeps track of
      who its parent is and who its children are.  A Node can only have 1
      parent and it can have 1 or many children.  In fact all of the
      information in a tree pertaining to the relationships between
      Nodes and specific data, like bootstrap values and labels, are all
      stored in the Node objects while the
      <emphasis>Bio::Tree::Tree</emphasis> object is just a 
      container for some summary information about the tree and a
      description of the tree's root node.
      </para>
      
   </section>
   <section id="simple_usage">
     <title>Simple Usage</title>
      <para>
      Trees are used to represent the history of a collection of taxa,
      sequences, or populations. 
      </para>
   </section>
   <section id="IO">
   <title>Reading and Writing Trees</title>
   <para>
      Using <emphasis>Bio::TreeIO</emphasis> one can read trees
      from files or datastreams and
      create <emphasis>Bio::Tree::Tree</emphasis> objects.  This is
      analagous to how we read sequences from sequence files with
      <emphasis>Bio::SeqIO</emphasis> to create Bioperl sequence
      objects which can be queried and manipulated.  Similarly we can
      write <emphasis>Bio::Tree::Tree</emphasis> objects out to string
      representations like the Newick or New Hampshire format which can
      be printed to a file, a datastream, stored in database, etc.
   </para>
   <para>
      The main module for reading and writing trees is the
      <emphasis>Bio::TreeIO</emphasis> factory module which has
      several driver modules which plug into it.  These drivers
      include <emphasis>Bio::TreeIO::newick</emphasis> for New
      Hampshire or Newick format,
      <emphasis>Bio::TreeIO::nhx</emphasis> for the New Hampshire eXtended
      format from Sean Eddy and Christian Zmeck as part of their RIO
      and ATV system [reference here].  The driver
      <emphasis>Bio::TreeIO::nexus</emphasis> supports parsing tree
      data from PAUP's Nexus format. However this driver currently
      only supports parsing, not writing, of Nexus format tree files.
   </para>
   </section>
   <section>
     <title>Example Code</title>
      <para>
      Here is some code which will read in a Tree from a file called
      "tree.tre" and produce a Bio::Tree::Tree object which is stored in 
      the variable <emphasis>$tree</emphasis>.
      </para>
      <para>
      Like most modules which do input/output you can also specify
      the argument -fh in place of -file to provide a glob or filehandle in
      place of the filename.  
      </para>
      <para>
      <programlisting>
      use Bio::TreeIO;
      # parse in newick/new hampshire format
      my $input = new Bio::TreeIO(-file   => "tree.tre",
                                  -format => "newick");
      my $tree = $input->next_tree;			       
      </programlisting>
      </para>
      <para>
      Once you have a Tree object you can do a number of things with it.
      These are all methods required in <emphasis>Bio::Tree::TreeI</emphasis>.
      </para>
      </section>

      <section id="TreeI">
       <title>Bio::Tree::TreeI methods</title>
        <para>
	Request the taxa (leaves of the tree).
	<programlisting>my @taxa = $tree->get_leaf_nodes;</programlisting>
	</para>

	<para>
	Get the root node.	
	<programlisting>my $root = $tree->get_root_node; </programlisting>
	</para>
	<para>
	Get the total length of the tree (sum of all the branch lengths),
	which is only useful if the nodes actually have the branch
	length stored, of course.
	<programlisting>my $total_length = $tree->total_branch_length;</programlisting>
	</para>
	
   </section>
   
   <section id="TreeFunctionsI">
    <title>Bio::Tree::TreeFunctionsI</title>
     <para>
     An additional interface was written which implements 
     utility functions which are useful for manipulating a Tree.
     </para>
     
     <para>
     Find a particular node, either by name or by some other field that is
     stored in a Node.  The field type should be the function name we
     can call on all of the Nodes in the Tree.
     <programlisting>
   # find all the nodes named 'node1' (there should be only one) 
   my @nodes = $tree->find_node(-id => 'node1');
   # find all the nodes which have description 'BMP'
   my @nodes = $tree->find_node(-description => 'BMP');
   # find all the nodes with bootstrap value of 70
   my @nodes = $tree->find_node(-bootstrap => 70);
   </programlisting>
   
     If you would like to do more sophisticated searches, like "find all
     the nodes with boostrap value better than 70", you can easily
     implement this yourself.
     <programlisting>
     my @nodes = grep { $_->bootstrap > 70 } $tree->get_nodes;
     </programlisting>

     Remove a Node from the Tree and update the children/ancestor links
     where the Node is an intervening one.
     <programlisting>
   # provide the node object to remove from the Tree
   $tree->remove_Node($node);
   # or specify the node Name to remove
   $tree->remove_Node('Node12');
   </programlisting>
 
    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.
 
   <programlisting>
   # Provide a list of Nodes that are in this tree
   my $lca = $tree->get_lca(-nodes => \@nodes);
   </programlisting>

   Get the distance between two nodes by adding up the branch lengths
   of all the connecting edges between two nodes.

   <programlisting>
   my $distances = $tree->distance(-nodes => [$node1,$node2]);
   </programlisting>

   Perform a test of 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.

   <programlisting>
   if( $tree->is_monophyletic(-nodes    => \@internal_nodes,
                              -outgroup => $outgroup) ) {
     print "these nodes are monophyletic: ",
          join(",",map { $_->id } @internal_nodes ), "\n";
   }
   </programlisting>
   
   Perform a test of paraphyly for a set of nodes and a given outgroup
   node.  This means that a common ancestor 'A' for the members of the
   group is more recent than a common ancestor 'B' that they share with
   the outgroup node <emphasis>and</emphasis> that there are no other 
	nodes in the tree which have 'A' as a common ancestor before 'B'.
   
   <programlisting>
   if( $tree->is_paraphyletic(-nodes    => \@internal_nodes,
                              -outgroup => $outgroup) ) {
     print "these nodes are monophyletic: ",
          join(",",map { $_->id } @internal_nodes ), "\n";
   }   
   </programlisting>   

   Reroot a tree, specifying a different node as the root (and a
   different node as the outgroup).
   <programlisting>
   # node can either be a Leaf node in which case it becomes the
   # outgroup and its ancestor is the new root of the tree
   # or it can be an internal node which will become the new
   # root of the Tree
   $tree->reroot($node);
   </programlisting>
   </para>
   </section>

   <section id="advanced_topics">
   <title>Advanced Topics</title>
   <para>
   It is possible to generate random tree topologies with a Bioperl
   object called <emphasis>Bio::Tree::RandomFactory</emphasis>.  The
   factory only requires the specification of the total number of taxa
   in order to simulate a history.  One can request different methods for
   generating the random phylogeny. At present, however, only the
   simple Yule backward is implemented and is the default. 
   </para>
   <para>
   The trees can be generated with the following code.  You can either
   specify the names of taxa or just a count of total number of taxa
   in the simulation.
   </para>
   <para>
   <programlisting>
   use Bio::TreeIO;
   use Bio::Tree::RandomFactory;
   # initialize a TreeIO writer to output the trees as we create them
   my $out = Bio::TreeIO->new(-format => 'newick',
                              -file   => ">randomtrees.tre");
   my @listoftaxa = qw(A B C D E F G H);			      
   my $factory = new Bio::Tree::RandomFactory(-taxa => \@listoftaxa);
   # generate 10 random trees
   for( my $i = 0; $i &lt; 10; $i++ ) {
      $out->write_tree($factory->next_tree);
   }
   # One can also just request a total number of taxa (8 here) and 
   # not provide labels for them
   # In addition one can specify the total number of trees
   # the object should return so we can call this in a while
   # loop
   $factory = new Bio::Tree::RandomFactory(-num_taxa => 8
                                           -max_count=> 10);
   while( my $tree = $factory->next_tree) {
     $out->write_tree($tree);
   }
   </programlisting>
   </para>			   	      
   <para>
   There are more sophisticated operations that you may wish to pursue
   with these objects.  We have tried to create a framework for this type
   of data, but by no means should this be looked at as the final
   product.  If you have a particular statistic or function that
   applies to trees that you would like to see included in the
   toolkit we encourage you to send details to the Bioperl list.
   </para>
   
   </section>
   <section id="References">
   <title>References and More Reading</title>
   <para>
   For more reading and some references for the techniques above see
   these titles.
   </para>   
   </section>
 </article> 
