edu.rit.compbio.phyl
Class MaximumParsimonyBnbSmp

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

public class MaximumParsimonyBnbSmp
extends Object

Class MaximumParsimonyBnbSmp provides an SMP parallel algorithm for maximum parsimony phylogenetic tree construction using branch-and-bound search.

Class MaximumParsimonyBnbSmp is designed to be used in an SMP parallel program that runs in one process with multiple threads. Each thread has its own MaximumParsimonyBnbSmp instance. Each thread uses its own MaximumParsimonyBnbSmp instance to search different sections of the search graph concurrently.

The process has a shared variable, bound, that holds the best parsimony score found so far (i.e., the bound for branch-and-bound search). The bound variable is an instance of class SharedInteger. All the MaximumParsimonyBnbSmp instances within the process share the same bound variable. Whenever one thread finds a phylogenetic tree with a better parsimony score, it notifies all the threads by updating the bound variable.

To perform a search, the process must:

1. Call the static createBoundVariable() method to create the shared bound variable.

Then each thread in the process must:

2. Create its own instance of class MaximumParsimonyBnbSmp, passing in a DnaSequenceList of the DNA sequences in the tree, a reference to the process's shared bound variable, and a MaximumParsimonyResults object to hold the search results.

3. Call the findTrees() method one or more times, each time indicating a section of the search graph to search. The results of searching that section are accumulated into the MaximumParsimonyResults object specified to the constructor.

Note: Class MaximumParsimonyBnbSmp is not multiple thread safe; it is intended to be used as a per-thread variable.

Constructor Summary

MaximumParsimonyBnbSmp(DnaSequenceList seqList, SharedInteger bound, MaximumParsimonyResults results)
Construct a new maximum parsimony phylogenetic tree construction algorithm object.

Method Summary

static SharedInteger	createBoundVariable(int initialBound) Create a new shared bound variable.
void	findTrees(int startLevel, int vertex1, int vertex2) Find the maximum parsimony phylogenetic tree(s) in the given section of the search graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

MaximumParsimonyBnbSmp

public MaximumParsimonyBnbSmp(DnaSequenceList seqList,
                              SharedInteger bound,
                              MaximumParsimonyResults results)

Construct a new maximum parsimony phylogenetic tree construction algorithm object.

Parameters:

seqList - DNA sequence list.

bound - Shared bound variable.

results - Object in which to store the results.

Method Detail

createBoundVariable

public static SharedInteger createBoundVariable(int initialBound)

Create a new shared bound variable.

Parameters:

initialBound - Initial bound for branch-and-bound search.

findTrees

public void findTrees(int startLevel,
                      int vertex1,
                      int vertex2)

Find the maximum parsimony phylogenetic tree(s) in the given section of the search graph. The DNA sequence list was specified to the constructor.

The search will commence at level L of the search graph, 0 ≤ L ≤ N−1, where N is the number of sequences in the DNA sequence list. Of the (2L−1)!! vertices at level L, the search will start at the V₁-th such vertex and end at the V₂-th such vertex, 0 ≤ V₁ ≤ V₂ ≤ (2L−1)!! − 1. All search graph vertices at and below vertices V₁ through V₂ inclusive will be searched.

The results are accumulated into the MaximumParsimonyResults object specified to the constructor. The findTrees() method will only find trees whose parsimony scores are less than or equal to the value of the bound variable specified to the constructor or the best bound found thereafter, whichever is smaller.

Parameters:

startLevel - L, the level of the search graph at which to commence the search.

vertex1 - V₁, the search graph vertex at level L at which to start the search.

vertex2 - V₂, the search graph vertex at level L at which to end the search.