edu.rit.compbio.phyl
Class DnaSequenceTree

java.lang.Object
  edu.rit.compbio.phyl.DnaSequenceTree

public class DnaSequenceTree
extends Object

Class DnaSequenceTree encapsulates a rooted bifurcating tree of DNA sequences. Each node in the tree is designated by an index from 0 to N−1, where N is the tree's length. The tree's capacity C is the maximum number of nodes (specified when the tree was constructed). For a tree to hold M tip nodes, the tree's capacity must be C ≥ 2M − 1.

Constructor Summary

DnaSequenceTree(int C)
Construct a new DNA sequence tree with the given capacity.

Method Summary

int	add(int i, DnaSequence seq) Add the given DNA sequence to this DNA sequence tree.
Double	branchLength(int i) Returns the branch length associated with the given node in this tree.
void	branchLength(int i, Double brlen) Set the branch length associated with the given node in this tree.
int	capacity() Returns the capacity of this tree.
int	child1(int i) Returns the first child of the given node in this tree.
int	child2(int i) Returns the second child of the given node in this tree.
void	clear() Clear this DNA sequence tree.
void	copy(DnaSequenceTree tree) Set this DNA sequence tree to be a copy of the given tree.
void	join(DnaSequenceTree tree1, DnaSequenceTree tree2) Set this DNA sequence tree to be the join of the two given trees.
int	length() Returns the length of this tree.
int	parent(int i) Returns the parent of the given node in this tree.
int	root() Returns the root of this tree.
DnaSequence	seq(int i) Returns the DNA sequence associated with the given node in this tree.
void	seq(int i, DnaSequence seq) Set the DNA sequence associated with the given node in this tree.
DnaSequenceList	toList() Create a DnaSequenceList consisting of the DNA sequences associated with the tip nodes in this tree.
String	toString() Returns a string version of this DNA sequence tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

DnaSequenceTree

public DnaSequenceTree(int C)

Construct a new DNA sequence tree with the given capacity. The new tree is initially empty.

Parameters:

C - Capacity.

Throws:

IllegalArgumentException - (unchecked exception) Thrown if C < 0.

Method Detail

capacity

public int capacity()

Returns the capacity of this tree.

Returns:

Capacity C (maximum number of nodes).

length

public int length()

Returns the length of this tree.

Returns:

Length N (number of nodes).

root

public int root()

Returns the root of this tree.

Returns:

Index of the root node, or −1 if this tree is empty.

parent

public int parent(int i)

Returns the parent of the given node in this tree.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

Returns:

Index of the parent of node i, or −1 if node i is the root node.

Throws:

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

child1

public int child1(int i)

Returns the first child of the given node in this tree.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

Returns:

Index of the first child of node i, or −1 if node i is a tip node.

Throws:

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

child2

public int child2(int i)

Returns the second child of the given node in this tree.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

Returns:

Index of the second child of node i, or −1 if node i is a tip node.

Throws:

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

seq

public DnaSequence seq(int i)

Returns the DNA sequence associated with the given node in this tree.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

Returns:

DNA sequence associated with node i, or null if no DNA sequence is associated.

Throws:

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

seq

public void seq(int i,
                DnaSequence seq)

Set the DNA sequence associated with the given node in this tree.

Note: The tree contains a reference to (not a copy of) seq.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

seq - DNA sequence associated with node i, or null if no DNA sequence is associated.

Throws:

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

branchLength

public Double branchLength(int i)

Returns the branch length associated with the given node in this tree.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

Returns:

Branch length between node i and its parent, or null if no branch length is associated.

Throws:

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

branchLength

public void branchLength(int i,
                         Double brlen)

Set the branch length associated with the given node in this tree.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

brlen - Branch length between node i and its parent, or null if no branch length is associated.

Throws:

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

clear

public void clear()

Clear this DNA sequence tree.

copy

public void copy(DnaSequenceTree tree)

Set this DNA sequence tree to be a copy of the given tree. This tree's capacity is unchanged and must be greater than or equal to the given tree's length. This tree's length, DNA sequences, and branch lengths become the same as tree.

Note: This tree contains references to (not copies of) the DNA sequences in tree.

Parameters:

tree - DNA sequence tree.

Throws:

NullPointerException - (unchecked exception) Thrown if tree is null.

IllegalArgumentException - (unchecked exception) Thrown if this tree's capacity is less than tree's length.

join

public void join(DnaSequenceTree tree1,
                 DnaSequenceTree tree2)

Set this DNA sequence tree to be the join of the two given trees. This tree's capacity is unchanged and must be greater than or equal to N₁ + N₂ + 1, where N₁ and N₂ are the two given trees' lengths. This tree's root node's first child becomes tree1. This tree's root node's second child becomes tree2. This tree's root node has no associated DNA sequence.

Note: This tree contains references to (not copies of) the DNA sequences in tree1 and tree2.

Note: Both tree1 and tree2 must be different objects from this tree.

Note: This method may alter the index of this tree's root node.

Parameters:

tree1 - First DNA sequence tree.

tree2 - Second DNA sequence tree.

Throws:

NullPointerException - (unchecked exception) Thrown if tree1 is null. Thrown if tree2 is null.

IllegalArgumentException - (unchecked exception) Thrown if this tree's capacity is less than N₁ + N₂ + 1.

add

public int add(int i,
               DnaSequence seq)

Add the given DNA sequence to this DNA sequence tree. This tree's capacity is unchanged and must be greater than or equal to this tree's length + 2. A new node is added to this tree. No DNA sequence is associated with the new node. The new node's parent is the parent of the node at index i; if the node at index i was the root node, the new node becomes the root node. The new node's first child is the node at index i. The new node's second child is a new tip node associated with the given DNA sequence.

Alternatively, if this tree is empty, the add() method sets this tree to have one root node associated with the given DNA sequence. In this case i is ignored.

Note: This tree contains a reference to (not a copy of) seq.

Note: This method may alter the index of this tree's root node.

Parameters:

i - Node index, 0 ≤ i ≤ N−1.

seq - DNA sequence associated with new tip node, or null if no DNA sequence is associated.

Returns:

Index of new tip node.

Throws:

IllegalArgumentException - (unchecked exception) Thrown if this tree's capacity is less than this tree's length + 2.

IndexOutOfBoundsException - (unchecked exception) Thrown if i is out of bounds.

toList

public DnaSequenceList toList()

Create a DnaSequenceList consisting of the DNA sequences associated with the tip nodes in this tree. The DNA sequences appear in descending order of the tip nodes' branch lengths. A tip node with no associated branch length uses a default branch length of 0.

Note: The returned list contains references to (not copies of) the DNA sequences in this tree.

Returns:

DNA sequence list.

toString

public String toString()

Returns a string version of this DNA sequence tree. The returned string is in Newick Standard format, including the branch lengths if any and the tip nodes' DNA sequence names. For further information about Newick Standard format, see:

• http://evolution.gs.washington.edu/phylip/newicktree.html

Overrides:

toString in class Object

Returns:

String version of this tree.