ptreegen.parsimony.LargeParsimony Class Reference

Represents a solution to the large parsimony problem (the tree toplogy is unknown as oposed to the small parsimony problem). More...

Public Member Functions
def	__init__
	Initializes the members used during the computation.
def	tree
	A getter for the obtained consensus tree.
def	cost
	A getter for the parsimony score of the computed tree.
def	quartetPuzzling
	Iteratively applies the quartet puzzling heuristic to obtain intermediate tree topologies.
def	getOptimalQuartets
	Finds the optimal topologies for every four taxa.

Static Public Member Functions
def	getQuartetID
	Provides a unique identification of the quartet by sorting the names of the taxa in the quartet alphabetically and then concatenating their identification strings, hence allowing quartets to be identified with their respective taxa.
def	getTopologyID
	Provides a string that uniquely identifies a quartet topology.
def	treeFromQuartet
	Constructs a tree from the provided quartet.
def	increaseCostOnPath
	Finds a path between two vertices and then increases the weight of all edges on that path by one.

Private Attributes
	_qpSteps
	The number of quartet puzzling steps to take.
	_alignment
	Reference to the multiple sequence alignment instance.
	_sequencesDict
	Associates sequence id string with a sequence instance.
	_optimalQuartets
	Associates every four taxa with their optimal quartet.
	_tree
	Reference to the tree that was computed in LargeParsimony::quartetPuzzling().

Detailed Description

Represents a solution to the large parsimony problem (the tree toplogy is unknown as oposed to the small parsimony problem).

It implements the quartet puzzling heuristic to find a set of possible tree topologies and it then builds a consensus tree employing the 50% majority rule (implemented in ptreegen::utilities::tree_utils::findConsensusTree()).

For more information on the quartet puzzling algorithm see:
Strimmer, Korbinian, and Arndt Von Haeseler. Quartet puzzling: a quartet maximum-likelihood method for reconstructing tree topologies. Molecular Biology and Evolution 13.7 (1996): 964-969.
or the appropriate chapter in:
Bockenhauer, H.; Bongartz, D. Algorithmic Aspects of Bioinformatics, 1st ed.; Springer: Berlin, 1998.

See Also

SmallParsimony

LargeParsimony::quartetPuzzling()

Definition at line 136 of file parsimony.py.

Constructor & Destructor Documentation

def ptreegen.parsimony.LargeParsimony.__init__	(		self,
			alignment,
			steps = 1000
	)

Initializes the members used during the computation.

It also generates the optimal quartets by first computing the parsimony cost of all possible unique quartet combinations and then selecting the quartet with minimum parsimony cost for every four taxa.

Parameters

alignment	multiple sequence alignment
steps	number of possible tree topologies that will be generated

Definition at line 147 of file parsimony.py.

    def __init__(self, alignment, steps=1000):
        self._qpSteps = int(steps)
        self._alignment = alignment
        self._sequencesDict = {x.id : x.seq for x in list(self._alignment)}
        quartet_combinations = []
        for combination in combination_utils.uniqueCombinationsGenerator(self._sequencesDict.keys(), 4):
            quartet_combinations.append(combination)
        self._optimalQuartets = self.getOptimalQuartets(quartet_combinations)
        self._tree = None