rapgreen

Class Tree

java.lang.Object

rapgreen.Tree

public class Tree
extends java.lang.Object

Global class of tree management.

This class contains every general method appliable to every type of trees, including pretreatment methods and fields to make quick comparisons.

A tree is defined recursively by a node. A node can be summered by a label, a length and a list of sons. So, the concept of node and tree are the same in this package.

The only supported format is the newick format. To construct trees from others format, please use the TreeReader class.

Field Summary

Fields

Modifier and Type	Field and Description
java.util.Hashtable	allowedLeft Allowed left constraints for tree pattern definition
java.util.Hashtable	allowedRight Allowed right constraints for tree pattern definition
Tree	father The father of this node.
java.util.Hashtable	forbiddenLeft v left constraints for tree pattern definition
java.util.Hashtable	forbiddenRight Forbidden right constraints for tree pattern definition
boolean	hasLeftConstraint Existence of right and left constraints
boolean	hasRightConstraint
java.lang.String	label The label of a node.
java.util.Hashtable	leafHashtable Hashtable containing leaf labels as keys, and leaves as information.
java.util.Vector	leafVector Vector containing leaves, in order to quickly be able to access them without step into the tree.
double	length The length of the branch upper this node.
double	maxDepth Precomputed max depth
java.lang.String	nhx The NHX String.
java.util.Vector	patternSpecies Allowed species for this pattern node / leaf
int	rightCardinalityMax Minimum cardinality for tree patter definition
int	rightCardinalityMin Minimum cardinality for tree patter definition
java.util.Vector	sons List of sons of this node.
java.lang.String	stringLength
boolean	ultra True if this node is an ultraparalogy node.

Constructor Summary

Constructors

Constructor and Description
Tree(java.lang.String newick) Generic constructor of a tree, from a newick string
Tree(Tree source) Cloning contructor, clone only basic fields, not the pretreatment fields
Tree(java.util.Vector sons, java.lang.String label, double length, java.lang.String nhx) Generic constructor of a node, directly from fields
Tree(java.util.Vector sons, java.lang.String label, double length, java.lang.String stringLength, java.lang.String nhx) Generic constructor of a node, directly from fields

Method Summary

Methods

Modifier and Type	Method and Description
void	addSpeciations() Add speciation events into every node
void	addUniquePrefix() Add prefixes to nodes in order to obtain unique ids as labels
void	clusteringNodes(java.util.Vector trees, double threshold) Fill a vector with nodes under a depth threshold
boolean	colorPattern(Tree pattern, Tree rootPattern, java.util.Hashtable ind, SpeciesDictionary dic, java.util.Vector colored, java.util.Hashtable stickers) Tree pattern coloration
java.util.Hashtable	computeExpansion(java.util.Hashtable d, java.util.Hashtable unrepresented) Return a table of the expansion for each node of this species tree
boolean	containsPattern(Tree pattern, java.util.Hashtable ind, SpeciesDictionary dic) Tree pattern detection
java.util.Hashtable	countCopies(java.util.Hashtable d, java.util.Hashtable l) Return a table of the number of ancestral copies for each node of this species tree
boolean	exclude(java.util.Vector list, java.util.Hashtable table, java.util.Hashtable excluded) Cut from the tree excluded taxa
void	fillAndCleanID(java.util.Hashtable table) Fill an ID table, deduced from labels, and clean leaf labels from Ids.
void	fillOrthologs(java.util.Vector allRes, java.util.Vector allDepth, java.util.Vector localRes) The subtree of a species tree, from this tree and a species list.
void	fillUltraParalogs(java.util.Hashtable table, java.util.Vector table2, int limit, java.util.Vector subspecies, java.util.Vector subspeciesTags, java.util.Hashtable globalTable) Fill a table with the largest ultraparalog group for each taxon
void	formatLabelsWithTrace() Clean labels, in order to fit the format P/S(trace)support
double	getDepth(Tree leaf) Return the depth of the leaf in this tree, 1.0 per level if no branch length, sum of branch lengths otherwise.
void	getDepths(java.util.Vector res, double save) Fill a vector with every depths of each leaf of the tree, from this node, adding save
void	getDuplications(java.util.Vector vect) Fill a vector with every duplication node of this tree.
void	getLosses(java.util.Vector vect) Fill a vector with every losses node of this tree.
int	getNbRedundancy() Return the number of redundant nodes.
void	getNbUltraparalogGroups(java.util.Hashtable table) Fill a table with the number of ultraparalogous groups for each taxon
java.lang.String	getNewick() Return the newick representation of this node
java.lang.String	getNHXNewick(Tree speciesTree, java.util.Hashtable duplications, java.lang.String refgroupe) Return the newick representation of this node
Tree	getNode(double targetLength, java.lang.String targetLabel) Return the node corresponding to length and label
java.util.Vector	getNodes() Return a vector containing all tree nodes under this node, this node included
java.util.Vector	getRootedTrees() Return every possible rooted trees, from this tree, cloning the structures
java.lang.String	getSimpleNewick() Return the simple (no length, no support) newick representation of this node
void	getSpeciations(java.util.Vector vect) Fill a vector with every speciations of leaves node of this tree.
void	globalPretreatment() Fill the Vector, Hashtable and pointer fields, for species trees
void	heavyPretreatment() Fill the Vector, Hashtable and pointer fields, in order to compare and reconcile this tree with others.
void	initializeDuplicationNatures() Check for each duplication if it is topological or intersection caused
boolean	isLeaf() Return true if this node is a leaf
Tree	lastCommonAncestor(Tree leafI, Tree leafJ) Return the last common ancestor of two leaves.
void	lightPretreatment() Fill the father field, in order to enrich steppings.
double	maxDepth() Return the max depth of the tree, 1.0 per level if no branch length, sum of branch lengths otherwise.
double	midpoint() Set root branch lengths as close as midpoint, and return a midpoint score.
int	nbIntersectionDuplications(Tree leaf)
int	nbLeaves() Return the number of leaves.
int	nbLosses() Return the number of losses of tree (LOSS label), reducing the number with internal losses
int	nbSpeciations(Tree leaf)
java.util.Vector	nbSpecies() Return an array of species
int	nbTopologicalDuplications(Tree leaf)
int	nbUltra(Tree leaf)
void	patternPretreatment(Tree speciesTree, SpeciesDictionary dico) Fill the Vector, Hashtable and pointer fields, in order to compare and reconcile this tree with others.
void	pretreatment() Fill the Vector, Hashtable and pointer fields, in order to compare and reconcile this tree with others.
boolean	reroot() Reroot the whole tree, father parents included, to the branch upper this node.
Tree	speciesMapping(Tree s)
java.util.Vector	speciesVector() Compute the species vector of this node
Tree	subtree(java.util.Hashtable species) The subtree of a species tree, from this tree and a species list.
int	subtreeNeighbor(int level) The subtree neighbor measure.
void	taxonomicPretreatment() Fill the Vector, Hashtable and pointer fields, in order to compare and a gene tree with a pattern tree.
java.lang.String	toPhyloXMLString(SpeciesDictionary dico) Specialized phyloXML string conversion method, used with a dictionary in order to generate a global species tree from NCBI files
java.lang.String	toPhyloXMLString(java.lang.StringBuffer buffer) Specialized phyloXML string conversion method
java.lang.String	toString() Standard string conversion method
double	trace() Compute the trace of a duplication node (intersection / union of species under the two sons)
java.util.Vector	traceVector() Compute the species intersection of this node
boolean	ultraParalogy() Return true if this subtree contains only paralogy, and false otherwise, and initialise the ultra attributes for the whole tree

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

sons

public java.util.Vector sons

List of sons of this node. An empty of null list implies that this node is a leaf.

label

public java.lang.String label

The label of a node. It can contains evolutionary, taxonomic or support information.

length

public double length

The length of the branch upper this node.

stringLength

public java.lang.String stringLength

nhx

public java.lang.String nhx

The NHX String.

leafHashtable

public java.util.Hashtable leafHashtable

Hashtable containing leaf labels as keys, and leaves as information. Available only after pretreatment.

leafVector

public java.util.Vector leafVector

Vector containing leaves, in order to quickly be able to access them without step into the tree. Available only after pretreatment.

maxDepth

public double maxDepth

Precomputed max depth

father

public Tree father

The father of this node. Available only after pretreatment.

ultra

public boolean ultra

True if this node is an ultraparalogy node.

allowedLeft

public java.util.Hashtable allowedLeft

Allowed left constraints for tree pattern definition

allowedRight

public java.util.Hashtable allowedRight

Allowed right constraints for tree pattern definition

forbiddenLeft

public java.util.Hashtable forbiddenLeft

v left constraints for tree pattern definition

forbiddenRight

public java.util.Hashtable forbiddenRight

Forbidden right constraints for tree pattern definition

rightCardinalityMin

public int rightCardinalityMin

Minimum cardinality for tree patter definition

rightCardinalityMax

public int rightCardinalityMax

Minimum cardinality for tree patter definition

patternSpecies

public java.util.Vector patternSpecies

Allowed species for this pattern node / leaf

hasLeftConstraint

public boolean hasLeftConstraint

Existence of right and left constraints

hasRightConstraint

public boolean hasRightConstraint

Constructor Detail

Tree

public Tree(java.lang.String newick)

Generic constructor of a tree, from a newick string

Parameters:

newick - The newick string, encoding the information

Tree

public Tree(java.util.Vector sons,
    java.lang.String label,
    double length,
    java.lang.String nhx)

Generic constructor of a node, directly from fields

Parameters:

sons - The sons of this node

label - The label of this node

length - The length of the branch upper this node

Tree

public Tree(java.util.Vector sons,
    java.lang.String label,
    double length,
    java.lang.String stringLength,
    java.lang.String nhx)

Generic constructor of a node, directly from fields

Parameters:

sons - The sons of this node

label - The label of this node

length - The length of the branch upper this node

Tree

public Tree(Tree source)

Cloning contructor, clone only basic fields, not the pretreatment fields

Parameters:

source - The node to clone

Method Detail

initializeDuplicationNatures

public void initializeDuplicationNatures()

Check for each duplication if it is topological or intersection caused

formatLabelsWithTrace

public void formatLabelsWithTrace()

Clean labels, in order to fit the format P/S(trace)support

speciesVector

public java.util.Vector speciesVector()

Compute the species vector of this node

Returns:

The species vector

traceVector

public java.util.Vector traceVector()

Compute the species intersection of this node

Returns:

The duplication species intersection

trace

public double trace()

Compute the trace of a duplication node (intersection / union of species under the two sons)

Returns:

The duplication trace

nbIntersectionDuplications

public int nbIntersectionDuplications(Tree leaf)

Parameters:

leaf - The leaf to starts from

Returns:

The number of topological incongruence duplication

nbTopologicalDuplications

public int nbTopologicalDuplications(Tree leaf)

Parameters:

leaf - The leaf to starts from

Returns:

The number of topological incongruence duplication

nbUltra

public int nbUltra(Tree leaf)

Parameters:

leaf - The leaf to starts from

Returns:

The number of ultraparalogy nodes

nbSpecies

public java.util.Vector nbSpecies()

Return an array of species

Returns:

The represented species

nbSpeciations

public int nbSpeciations(Tree leaf)

Parameters:

leaf - The leaf to starts from

Returns:

The number of speciation nodes

subtreeNeighbor

public int subtreeNeighbor(int level)

The subtree neighbor measure. The tree must be pretreated.

Parameters:

level - The k-level

Returns:

The k-value

getDepths

public void getDepths(java.util.Vector res,
             double save)

Fill a vector with every depths of each leaf of the tree, from this node, adding save

Parameters:

res - the vector to fill

save - the value to add, 0.0 if executed from the root

speciesMapping

public Tree speciesMapping(Tree s)

Parameters:

s - The full species tree

Returns:

The linked species tree node, LSA of this tree species

subtree

public Tree subtree(java.util.Hashtable species)

The subtree of a species tree, from this tree and a species list.

Parameters:

species - the species table

Returns:

the newly created subtree

fillOrthologs

public void fillOrthologs(java.util.Vector allRes,
                 java.util.Vector allDepth,
                 java.util.Vector localRes)

The subtree of a species tree, from this tree and a species list.

Parameters:

allRes - vector to fill

localRes - must be initialised to new Vector

getLosses

public void getLosses(java.util.Vector vect)

Fill a vector with every losses node of this tree.

Parameters:

vect - the vector to fill-

getSpeciations

public void getSpeciations(java.util.Vector vect)

Fill a vector with every speciations of leaves node of this tree.

Parameters:

vect - the vector to fill-

getDuplications

public void getDuplications(java.util.Vector vect)

Fill a vector with every duplication node of this tree.

Parameters:

vect - the vector to fill-

getNode

public Tree getNode(double targetLength,
           java.lang.String targetLabel)

Return the node corresponding to length and label

Returns:

The target node

nbLosses

public int nbLosses()

Return the number of losses of tree (LOSS label), reducing the number with internal losses

Returns:

The number of losses

toString

public java.lang.String toString()

Standard string conversion method

Overrides:

toString in class java.lang.Object

Returns:

The string translation.

addSpeciations

public void addSpeciations()

Add speciation events into every node

containsPattern

public boolean containsPattern(Tree pattern,
                      java.util.Hashtable ind,
                      SpeciesDictionary dic)

Tree pattern detection

Parameters:

pattern - The pattern to detect

ind - The species index

dic - The species dictionary

Returns:

True if the pattern is in the tree, false overthise

colorPattern

public boolean colorPattern(Tree pattern,
                   Tree rootPattern,
                   java.util.Hashtable ind,
                   SpeciesDictionary dic,
                   java.util.Vector colored,
                   java.util.Hashtable stickers)

Tree pattern coloration

Parameters:

pattern - The pattern to detect

ind - The species index

dic - The species dictionary

Returns:

True if the pattern is in the tree, false overthise

exclude

public boolean exclude(java.util.Vector list,
              java.util.Hashtable table,
              java.util.Hashtable excluded)

Cut from the tree excluded taxa

Parameters:

list - the vector of excluded taxa

table - the hashtable of excluded taxa

excluded - the hashtable hashtable of excluded sequences, filled during the process

Returns:

true if the tree is not empty, false otherwise.

toPhyloXMLString

public java.lang.String toPhyloXMLString(java.lang.StringBuffer buffer)

Specialized phyloXML string conversion method

Parameters:

buffer - sequence relations

Returns:

The string translation.

toPhyloXMLString

public java.lang.String toPhyloXMLString(SpeciesDictionary dico)

Specialized phyloXML string conversion method, used with a dictionary in order to generate a global species tree from NCBI files

Parameters:

dico - The species dictionary

Returns:

The string translation.

midpoint

public double midpoint()

Set root branch lengths as close as midpoint, and return a midpoint score.

Returns:

The midpoint score

lightPretreatment

public void lightPretreatment()

Fill the father field, in order to enrich steppings.

clusteringNodes

public void clusteringNodes(java.util.Vector trees,
                   double threshold)

Fill a vector with nodes under a depth threshold

Parameters:

trees - The vector to fill

threshold - The cutting threshold

heavyPretreatment

public void heavyPretreatment()

Fill the Vector, Hashtable and pointer fields, in order to compare and reconcile this tree with others. Add node labels.

taxonomicPretreatment

public void taxonomicPretreatment()

Fill the Vector, Hashtable and pointer fields, in order to compare and a gene tree with a pattern tree. Store only taxonomic information (XX_TAXON) in data structures.

patternPretreatment

public void patternPretreatment(Tree speciesTree,
                       SpeciesDictionary dico)

Fill the Vector, Hashtable and pointer fields, in order to compare and reconcile this tree with others.

globalPretreatment

public void globalPretreatment()

Fill the Vector, Hashtable and pointer fields, for species trees

pretreatment

public void pretreatment()

Fill the Vector, Hashtable and pointer fields, in order to compare and reconcile this tree with others.

fillAndCleanID

public void fillAndCleanID(java.util.Hashtable table)

Fill an ID table, deduced from labels, and clean leaf labels from Ids. Usable for some specialized species trees

Parameters:

table - The id table to fill

ultraParalogy

public boolean ultraParalogy()

Return true if this subtree contains only paralogy, and false otherwise, and initialise the ultra attributes for the whole tree

Returns:

True if this is an ultraparalogy node, false otherwise

fillUltraParalogs

public void fillUltraParalogs(java.util.Hashtable table,
                     java.util.Vector table2,
                     int limit,
                     java.util.Vector subspecies,
                     java.util.Vector subspeciesTags,
                     java.util.Hashtable globalTable)

Fill a table with the largest ultraparalog group for each taxon

Parameters:

table - The table to fill

table2 - The id table to fill

limit - the minimum number of ultraparalog in a group to fill the ids table

getNbUltraparalogGroups

public void getNbUltraparalogGroups(java.util.Hashtable table)

Fill a table with the number of ultraparalogous groups for each taxon

Parameters:

table - The table to fill

getNHXNewick

public java.lang.String getNHXNewick(Tree speciesTree,
                            java.util.Hashtable duplications,
                            java.lang.String refgroupe)

Return the newick representation of this node

Returns:

The newick standard representation of this node

getNewick

public java.lang.String getNewick()

Return the newick representation of this node

Returns:

The newick standard representation of this node

getSimpleNewick

public java.lang.String getSimpleNewick()

Return the simple (no length, no support) newick representation of this node

Returns:

The newick standard representation of this node

maxDepth

public double maxDepth()

Return the max depth of the tree, 1.0 per level if no branch length, sum of branch lengths otherwise.

Returns:

The max depth

getDepth

public double getDepth(Tree leaf)

Return the depth of the leaf in this tree, 1.0 per level if no branch length, sum of branch lengths otherwise.

Parameters:

leaf - The target leaf

Returns:

The depth

lastCommonAncestor

public Tree lastCommonAncestor(Tree leafI,
                      Tree leafJ)

Return the last common ancestor of two leaves.

Parameters:

leafI - The first leaf

leafJ - The second leaf

Returns:

The last common ancestor of leafI and leafJ

getNbRedundancy

public int getNbRedundancy()

Return the number of redundant nodes.

Returns:

The number of redundant nodes

isLeaf

public boolean isLeaf()

Return true if this node is a leaf

Returns:

True if this node is a leaf and false if this node is internal

computeExpansion

public java.util.Hashtable computeExpansion(java.util.Hashtable d,
                                   java.util.Hashtable unrepresented)

Return a table of the expansion for each node of this species tree

Returns:

The tree nodes

addUniquePrefix

public void addUniquePrefix()

Add prefixes to nodes in order to obtain unique ids as labels

countCopies

public java.util.Hashtable countCopies(java.util.Hashtable d,
                              java.util.Hashtable l)

Return a table of the number of ancestral copies for each node of this species tree

Returns:

The tree nodes

getNodes

public java.util.Vector getNodes()

Return a vector containing all tree nodes under this node, this node included

Returns:

The tree nodes

getRootedTrees

public java.util.Vector getRootedTrees()

Return every possible rooted trees, from this tree, cloning the structures

Returns:

A vector of rooted trees

nbLeaves

public int nbLeaves()

Return the number of leaves.

Returns:

The number of leaves

reroot

public boolean reroot()

Reroot the whole tree, father parents included, to the branch upper this node.

Returns:

True if the tree needed to be rerooted, false if it were already rooted at the right place