edu.rit.compbio.phyl
Class MaximumParsimonyBnbHyb

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

public class MaximumParsimonyBnbHyb
extends Object

Class MaximumParsimonyBnbHyb provides a hybrid parallel algorithm for maximum parsimony phylogenetic tree construction using branch-and-bound search.

Class MaximumParsimonyBnbHyb is designed to be used in a hybrid parallel program that runs on multiple nodes with one process per node and multiple threads per process. Each thread has its own MaximumParsimonyBnbHyb instance. Each thread uses its own MaximumParsimonyBnbHyb instance to search different sections of the search graph concurrently.

Each process has a shared, replicated 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 ReplicatedInteger. All the MaximumParsimonyBnbHyb 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 and processes by updating the bound variable.

To perform a search, each process must:

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

Then each thread in each process must:

2. Create its own instance of class MaximumParsimonyBnbHyb, passing in a DnaSequenceList of the DNA sequences in the tree, a reference to the process's shared, replicated 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 MaximumParsimonyBnbHyb is not multiple thread safe; it is intended to be used as a per-thread variable.

Constructor Summary

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

Method Summary

static ReplicatedInteger	createBoundVariable(int initialBound) Create a new shared, replicated bound variable.
static ReplicatedInteger	createBoundVariable(int initialBound, Comm comm, int tag) Create a new shared, replicated 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

MaximumParsimonyBnbHyb

public MaximumParsimonyBnbHyb(DnaSequenceList seqList,
                              ReplicatedInteger bound,
                              MaximumParsimonyResults results)

Construct a new maximum parsimony phylogenetic tree construction algorithm object.

Parameters:

seqList - DNA sequence list.

bound - Shared, replicated bound variable.

results - Object in which to store the results.

Method Detail

createBoundVariable

public static ReplicatedInteger createBoundVariable(int initialBound)

Create a new shared, replicated bound variable. The bound variable will use the world communicator and a message tag of Integer.MAX_VALUE. This message tag must not be used in any other messages in the program.

Parameters:

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

createBoundVariable

public static ReplicatedInteger createBoundVariable(int initialBound,
                                                    Comm comm,
                                                    int tag)

Create a new shared, replicated bound variable.

Parameters:

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

comm - Communicator used by the bound variable.

tag - Message tag used by the bound variable. This message tag must not be used in any other messages in the program.

findTrees

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

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 stored in 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.

Throws:

IOException - Thrown if an I/O error occurred.