PSODA Architecture

PSODA Architecture

9/19/06

 

This document provides an overview of the software architecture for the PSODA phylogenetic analysis package.  The software is divided into 4 major pieces:

• The parser is started by main.cc to parse the .nex file.  The parser will then call the doHeuristicSearch method in Interpreter.cpp.  Utility objects such as QTree, QNode, QTreeRepository are found in the src directory.
• Evaluators determine how to score the tree.  In the src/evaluators directory, you can find Parsimony.cpp along with future work with maximum likelihood and optimization alignment evaluation methods.
• Algorithms determine how the tree is rearranged.  QTBR is the primary algorithm for doing branch swapping.
• Searches determine what to do with the rearranged trees.  A search will call the algorithm with an evaluator.  The algorithm will return a list of trees that have been found and the search can put them in the repository with different selection methods.

 

This figure provides an overall architecture for the software:

 

Each virtex of the tree consists of QNode objects.  Each of these objects has an internal pointer to other Qnodes in this virtex, and an external pointer to QNode objects in other virtices.  The direction of the parent and children of this virtex depends on how the tree is viewed.  Each external pointer can point to a parent or a child in the tree structure.

 

 

 

 

 

 

 

 

In order to make a tree, you connect the external pointers from two virtices to allow for flexible traversal.  Single QNode objects represent leaves of the tree.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Algorithms for rearranging the tree are in the "algorithms" directory.  Each of these classes should have a rearrange method.  This method accepts a tree, an evaluator, and a dataset as parameters.  You can also specify whether you want the rearrangement to destroy the current tree (for stepwise addition) or make a copy.  The rearrange method will call the evaluator to score the tree and the evaluator needs the dataset.

 

Searches are found in the "searches" directory includes stepwise addition and QretainedResultsSearch.  Searches must implement the "search" method that takes a tree repository, an algorithm, an evaluator, a dataset and the number of iterations you want it to search for.  Searches really just call the rearrange method on the algorithm and pass it the rest of the parameters it needs.

 

The "parsers" directory contains the parsers for nexus files and tree files.  Control initially goes to the parser, then the parser calls routines in the Interpreter.cpp file to make things happen. 

 

The "evaluators" directory contains code to score trees.  Evaluators such as parsimony should implement preProcess  and evaluateTree to score rearrangements during branch swapping.  They should also include scoreTree to score a tree from scratch.

 

During a search, the tree repository is initialized with a start tree (maybe the result of a stepwise search).  The search then gets the best tree out of the repository and calls the algorithm's rearange method on that tree.  The rearange method returns a list of trees that all have the best score found in the rearrangement.  If  the score is better than the previous best score found in the repository, then the search nukes everything in the repository and puts the list of better trees in. Once a tree has been fully searched, the search puts it back in the repository with the visited state set.  When all trees in the repository have been fully searched and no better trees have been found, the search terminates.