QuartetJoining

class QuartetJoining(theTrees)

Mark Wilkinson’s fast supertree method.

You feed this a list of p4 Tree objects.

For example. read(‘myTreeFile.nex’) qj = QuartetJoining(var.trees) qj.useAnInputTreeAsTheStartingTree = True qj.doBreakTies = True qj.doPips=True qj.maxQuartetsPerN = 0 qj.doAddXSubTree = True qjt = qj.quartetJoining() qjt.writeNexus(‘myQJTree.nex’)

addLeafToBigT(theNode, x)

addUnusedTaxaIfTheyHaveThreeKBrs()

addXSubTreeToBigT(theNode, x)

allChooseFour(things)

breakTie()

calculateBitKeyForInternalNodeFromChildren(theNode)

checkBigTInternalNodes()

checkBitKeys(theTree)

collapseNodesAndAddUnusedTaxa()

decorateTreeWithBitKeys(theTree)

Put bitKey attributes on all branches of the tree.

bitKey’s are attributes of node branches, and are binary numbers that say what taxa are above that branch in the tree.

dump(fName=None)

Dump info and options about self.

getAnInputTreeForTheStartingTree()

getKNodes(theNode)

Find and return the kIntNodes and kBrs in the k-subtree.

getQuartetForFourTaxaInTrees(taxa, theTrees)

getQuartetsForXForNode(x, theNode)

getStartingTreeFromQuartet()

getStartingTreeFromQuartet_highFrequencyFirst()

getStartingTreeFromQuartet_randomTaxa()

getTaxBitsString(taxBits)

locateAndCountLeavesInXSubTreeFromQuartet(q, x)

Find the node in the q.tree with the x-subtree, and count leaves.

We also find the xNode, the node in q.tree at which the x-subtree can be taken, and ‘up’, which says whether that x-subtree goes up or down from that xNode. Both of these become attributes of q, the QJQuartet object. The leaf count is returned.

makeStartingQuartetFromAllTrees(theOriginalTree, twoNodesAbove, twoNodesBelow, fourTaxa)

Having chosen fourTaxa, get quartets from all input trees, and make a staring quartet.

property nTax

(property) Return the number of taxa

property nTrees

(property) Return the number of input trees

pause()

popcount(n)

quartetJoining(verbose=True)

Do The quartet joining method.

This returns a Tree object (bigT), which either has all the taxa, or not. It has a list of unusedTaxa attached, and if that list is empty then it has all the taxa. On the other hand if the supertree is incomplete then there are Tax objects in that list, each of which contains a list of nodes on bigT on which the leftover taxon could go.

If you set verbose=True for this method (which is different from setting verbose for the whole QuartetJoining instance) then it will tell you if it gets a complete tree or not, and if not it will make a table of taxa that did not make it into the supertree, and the branches on which they could go.

You can test if you have a complete tree by asking the tree that is returned whether it has any unusedTaxa, eg if you call your tree ‘qt’ you can ask

if qt.unusedTaxa:

<it is incomplete>

else:

<its a complete supertree>

refineKSubTree(kIntNodes, kBrs, x, internalNodesWithNoQuartets)

setTreeTaxBits(theTree)

This needs to have bitKey attributes for nodes already set.

taxBits says which of self.taxa are in theTree.

summarizeUnusedTaxa(leftOverTaxNames=None)

tryToAddAParticularX(x)

Given a particular x, try to add it.

This method tries to add the particular x ‘centered’ on all the internal nodes in bigT, until success or until it runs out of internal nodes in bigT.

It returns a list of branches on bigT where x could be added. The list contains at least 1 item, but may contain more.

tryToAddAnyX()

Add any one of the unused taxa.

This is called only by the main loop in the quartetJoining() method.

Its an infinite loop, and the only way to get out of it is to add a taxon to bigT or to run out of choices.

First choose a random x. Having chosen an x, we invoke the method tryToAddAParticularX(). This will return either None or a list, kBrs, with at least one item in it. KBrs are branches in bigT where x might be added. Ideally, the list of kBrs will have only one item, the branch on the k-subtree on bigT where the x should be added. But often it returns a list with 2 or more, meaning that it is ambiguous. If so, we move on to the next x.

If tryToAddAParticularX() returns a single kBr, then we add that leaf (x) to bigT at kBr. If doAddXSubTree is turned on, then an x-subtree is added.