edu.rit.compbio.phyl

Class FitchParsimony

java.lang.Object

edu.rit.compbio.phyl.FitchParsimony

public class FitchParsimony
extends java.lang.Object

Class FitchParsimony provides the Fitch algorithm for computing the parsimony score of a DnaSequenceTree. For further information, see:

• W. Fitch. Toward defining the course of evolution: minimum change for a specified tree topology. Systematic Zoology, 20:406-416, 1971.
• J. Felsenstein. Inferring Phylogenies. Sinauer Associates, 2004, pages 11-13.

Method Summary

Modifier and Type	Method and Description
static int	computeScore(DnaSequenceTree tree) Compute the Fitch parsimony score of the given DNA sequence tree.
static int	updateScore(DnaSequenceTree tree, int tip, DnaSequence[] seqarray) Update the Fitch parsimony score of the given DNA sequence tree, from the given tip node up to the root.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

computeScore

public static int computeScore(DnaSequenceTree tree)

Compute the Fitch parsimony score of the given DNA sequence tree. Call computeScore() to compute the score for an entire tree.

When computeScore() is called:

• Every tip node in tree must be associated with a DNA sequence whose score is 0.
• Every interior node in tree may or may not be associated with a DNA sequence.
• All DNA sequences in tree must be the same length.

When computeScore() returns:

• Every tip node's DNA sequence is unchanged.
• Every interior node that had not been associated with a DNA sequence is associated with a newly created DNA sequence.
• Every interior node's DNA sequence has been set to an intermediate value as determined by the Fitch algorithm, and the DNA sequence's name has been set to the number of state changes at that node.
• The root node's DNA sequence's score is the tree's Fitch parsimony score. The score is also returned.

Parameters:

tree - DNA sequence tree.

Returns:

Fitch parsimony score of tree.

updateScore

public static int updateScore(DnaSequenceTree tree,
                              int tip,
                              DnaSequence[] seqarray)

Update the Fitch parsimony score of the given DNA sequence tree, from the given tip node up to the root. Call updateScore() to re-compute the score when a tip node is added to the tree; this takes less time than re-computing the score for the entire tree.

When updateScore() is called:

• The node at index tip and its parent node must have been just added by the DnaSequenceTree.add() method.
• The node at index tip must be associated with a DNA sequence whose score is 0.
• All other nodes in tree must be associated with a DNA sequence containing a Fitch parsimony score, as computed by a previous call of computeScore() or updateScore().
• All DNA sequences in tree must be the same length.

When computeScore() returns:

• Every interior node on the path from the node at index tip to the root node is associated with one of the sequences in seqarray. If there are N tip nodes in the tree, there must be at least N−1 DNA sequences in seqarray.
• Every interior node's DNA sequence on the path from the node at index tip to the root node has been set to an intermediate value as determined by the Fitch algorithm.
• The root node's DNA sequence's score is the tree's Fitch parsimony score. The score is also returned.

Parameters:

tree - DNA sequence tree.

tip - Index of just-added tip node.

seqarray - Array of DNA sequences to be associated with interior nodes.

Returns:

Fitch parsimony score of tree.