FORESTER 1.92

forester.tools
Class OE

java.lang.Object
  |
  +--forester.tools.SDI
        |
        +--forester.tools.OE

public class OE
extends SDI

Implements Oliver Eulenstein's algorithm for speciation - duplication inference.

References:

The initialization is accomplished by:

The recursion part is accomplished by method "DFS(Node)" of this class

Duplication and speciations are determined by "determine(Node)" of this class.

Requires JDK 1.2 or greater.

Version:
1.012 -- last modified: 10/02/01
Author:
Christian M. Zmasek
See Also:
SDI.stripTree(Tree,Tree), Tree.preorderReID(int), Tree.hashIDs(), Tree.setIndicatorsToZero(), linkExtNodesOfS(), DFS(Node), determine(Node)

Constructor Summary
OE(Tree gene_tree, Tree species_tree)
          Constructor which sets the gene tree and the species tree to be compared.
 
Method Summary
 int computeMappingCost()
          Computes the cost of mapping the gene tree gene_tree onto the species tree species_tree.
(package private)  void determine(Node g)
          Determines which nodes of the subtree of gene tree node g represent duplications and which ones speciations.
(package private)  void DFS(Node s)
          Traverses the species tree in postorder.
 int infer(boolean strip_species_tree)
          Infers for each Node of gene_tree (set in constructor) whether it represents a speciation or duplication event by calculating and interpreting the mapping function M.
(package private)  void linkExtNodesOfS()
          Links each external Node of the species tree to the all external nodes of the gene tree which have the same species name.
 
Methods inherited from class forester.tools.SDI
decreaseDuplications, getDuplications, getGeneTree, getMappingCost, getSpeciesTree, increaseDuplications, linkExtNodesOfG, main, setDuplicationsToZero, stripTree
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

OE

public OE(Tree gene_tree,
          Tree species_tree)
   throws java.lang.Exception
Constructor which sets the gene tree and the species tree to be compared. species_tree is the species tree to which the gene tree gene_tree will be compared to - with method "infer(boolean)". Both Trees must be completely binary and rooted. The actual inference is accomplished with method "infer(boolean)". The mapping cost L can then be calculated with method "computeMappingCost()".
(Last modified: 01/11/01)
Parameters:
gene_tree - reference to a rooted binary gene Tree to which assign duplication vs speciation, must have species names in the species name fields for all external nodes
species_tree - reference to a rooted binary species Tree which might get stripped in the process, must have species names in the species name fields for all external nodes
See Also:
infer(boolean), computeMappingCost()
Method Detail

infer

public int infer(boolean strip_species_tree)
          throws java.lang.Exception
Infers for each Node of gene_tree (set in constructor) whether it represents a speciation or duplication event by calculating and interpreting the mapping function M. The most parsimonious sequence of speciation and duplication events is assumed.

The species tree MUST NOT contain species not found in the gene tree. If it does, set strip_species_tree to true.

(Last modified: 01/11/01)

Overrides:
infer in class SDI
Parameters:
strip_species_tree - set to true if species are present in the species tree which are not in the gene tree (not optional!)
Returns:
number of duplications which have been assigned in gene_tree

computeMappingCost

public int computeMappingCost()
                       throws java.lang.Exception
Computes the cost of mapping the gene tree gene_tree onto the species tree species_tree. Before this method can be called, the mapping has to be calculated with method "infer(boolean)".

Overrides the method of the base class, since additionaly the links for the gene tree have to be calculated first.

Reference. Zhang, L. (1997) On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies. Journal of Computational Biology 4 177-187.

(Last modified: 11/07/00)

Overrides:
computeMappingCost in class SDI
Returns:
the mapping cost "L"

DFS

void DFS(Node s)
Traverses the species tree in postorder. Creates Baskets for each external node.

(Last modified: 01/11/01)


linkExtNodesOfS

void linkExtNodesOfS()
               throws java.lang.Exception
Links each external Node of the species tree to the all external nodes of the gene tree which have the same species name.

The matching Nodes of the gene tree are placed in a Vector associated with each external Nodes of the species tree. This is necessary in order to deal with redundant species in the gene tree and is not part of the algorithm as described in Eulenstein (1998), but it is mentioned in Eulenstein (1996).

(Last modified: 01/11/01)


determine

void determine(Node g)
Determines which nodes of the subtree of gene tree node g represent duplications and which ones speciations.

Precondition: Mapping function M for all nodes of the gene tree must have been calculated.

(Last modified: 01/11/01)

Parameters:
g - starting node of a gene tree - normally the root

FORESTER 1.92