Functions
Topological rearrangements

Functions

pllRearrangeListpllCreateRearrangeList (int max)
 Create a list for storing topology rearrangements. More...
 
void pllDestroyRearrangeList (pllRearrangeList **bestList)
 Deallocator for topology rearrangements list. More...
 
int pllRearrangeRollback (pllInstance *tr, partitionList *pr)
 Rollback the last committed rearrangement move. More...
 
void pllRearrangeCommit (pllInstance *tr, partitionList *pr, pllRearrangeInfo *rearr, int saveRollbackInfo)
 Commit a rearrangement move. More...
 
void pllRearrangeSearch (pllInstance *tr, partitionList *pr, int rearrangeType, nodeptr p, int mintrav, int maxtrav, pllRearrangeList *bestList)
 Search for rearrangement topologies. More...
 

Static functions

static int pllStoreRearrangement (pllRearrangeList *bestList, pllRearrangeInfo *rearr)
 Store a rearrangement move to the list of best rearrangement moves. More...
 
static int pllTestInsertBIG (pllInstance *tr, partitionList *pr, nodeptr p, nodeptr q, pllRearrangeList *bestList)
 Internal function for testing and saving an SPR move. More...
 
static void pllTraverseUpdate (pllInstance *tr, partitionList *pr, nodeptr p, nodeptr q, int mintrav, int maxtrav, pllRearrangeList *bestList)
 Internal function for recursively traversing a tree and testing a possible subtree insertion. More...
 
static int pllTestSPR (pllInstance *tr, partitionList *pr, nodeptr p, int mintrav, int maxtrav, pllRearrangeList *bestList)
 Internal function for computing SPR moves. More...
 
static void pllComputeSPR (pllInstance *tr, partitionList *pr, nodeptr p, int mintrav, int maxtrav, pllRearrangeList *bestList)
 Compute a list of possible SPR moves. More...
 
static double pllTestNNILikelihood (pllInstance *tr, partitionList *pr, nodeptr p, int swapType)
 Return the yielded likelihood of an NNI move, without altering the topology. More...
 
static void pllTestNNI (pllInstance *tr, partitionList *pr, nodeptr p, pllRearrangeList *bestList)
 Compares NNI likelihoods at a node and store in the rearrangement list. More...
 
static void pllTraverseNNI (pllInstance *tr, partitionList *pr, nodeptr p, int mintrav, int maxtrav, pllRearrangeList *bestList)
 Recursive traversal of the tree structure for testing NNI moves. More...
 
static void pllSearchNNI (pllInstance *tr, partitionList *pr, nodeptr p, int mintrav, int maxtrav, pllRearrangeList *bestList)
 Compute a list of possible NNI moves. More...
 
static void pllCreateSprInfoRollback (pllInstance *tr, pllRearrangeInfo *rearr, int numBranches)
 Create rollback information for an SPR move. More...
 
static void pllCreateNniInfoRollback (pllInstance *tr, pllRearrangeInfo *rearr)
 Create rollback information for an NNI move. More...
 
static void pllCreateRollbackInfo (pllInstance *tr, pllRearrangeInfo *rearr, int numBranches)
 Generic function for creating rollback information. More...
 
static void pllRollbackSPR (pllInstance *tr, partitionList *pr, pllRollbackInfo *ri)
 Rollback an SPR move. More...
 
static void pllRollbackNNI (pllInstance *tr, partitionList *pr, pllRollbackInfo *ri)
 Rollback an NNI move. More...
 

Detailed Description

This set of functions handles the rearrangement of the tree topology

Function Documentation

static void pllComputeSPR ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  mintrav,
int  maxtrav,
pllRearrangeList bestList 
)
static

Compute a list of possible SPR moves.

Iteratively tries all possible SPR moves that can be performed by pruning the subtree rooted at p and testing all possible placements in a radius of at least mintrav nodea and at most maxtrav nodes from p. Note that tr->thoroughInsertion affects the behaviour of the function (see note).

Parameters
trPLL instance
prList of partitions
pNode specifying the root of the pruned subtree, i.e. where to prune.
mintravMinimum distance from p where to try inserting the pruned subtree
maxtravMaximum distance from p where to try inserting the pruned subtree
Note
Setting tr->thoroughInsertion affects this function. For each tested SPR the new branch lengths will also be optimized. This computes better likelihoods but also slows down the method considerably.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pllCreateNniInfoRollback ( pllInstance tr,
pllRearrangeInfo rearr 
)
static

Create rollback information for an NNI move.

Creates a structure of type pllRollbackInfo and fills it with rollback information about the SPR move described in rearr. The rollback info is stored in the PLL instance in a LIFO manner

Parameters
trPLL instance
rearrDescription of the NNI move

+ Here is the caller graph for this function:

pllRearrangeList* pllCreateRearrangeList ( int  max)

Create a list for storing topology rearrangements.

Allocates space and initializes a structure that will hold information of max topological rearrangements

Parameters
maxMaximum number of elements that the structure should hold
Note
This should be called for creating a storage space (list) for routines such as pllRearrangeSearch which compute the best NNI/PR/TBR rearrangements.
static void pllCreateRollbackInfo ( pllInstance tr,
pllRearrangeInfo rearr,
int  numBranches 
)
static

Generic function for creating rollback information.

Creates a structure of type pllRollbackInfo and fills it with rollback information about the move described in rearr. The rollback info is stored in the PLL instance in a LIFO manner

Parameters
trPLL instance
rearrDescription of the NNI move
numBranchesNumber of partitions

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pllCreateSprInfoRollback ( pllInstance tr,
pllRearrangeInfo rearr,
int  numBranches 
)
static

Create rollback information for an SPR move.

Creates a structure of type pllRollbackInfo and fills it with rollback information about the SPR move described in rearr. The rollback info is stored in the PLL instance in a LIFO manner.

Parameters
trPLL instance
rearrDescription of the SPR move
numBranchesNumber of partitions

+ Here is the caller graph for this function:

void pllDestroyRearrangeList ( pllRearrangeList **  bestList)

Deallocator for topology rearrangements list.

Call this to destroy (deallocate) the memory taken by the bestList which holds topological rearrangements

Parameters
bestListPointer to the list to be deallocated
void pllRearrangeCommit ( pllInstance tr,
partitionList pr,
pllRearrangeInfo rearr,
int  saveRollbackInfo 
)

Commit a rearrangement move.

Applies the rearrangement move specified in rearr to the tree topology in tr. In case of SPR moves, if tr->thoroughInsertion is set to PLL_TRUE, the new branch lengths are also optimized. The function stores rollback information in pllInstance::rearrangeHistory if saveRollbackInfo is set to PLL_TRUE. This way, the rearrangement move can be rolled back (undone) by calling pllRearrangeRollback

Parameters
trPLL instance
prList of partitions
rearrAn element of a pllRearrangeInfo structure that contains information about the rearrangement move
saveRollbackInfoIf set to PLL_TRUE, rollback info will be kept for undoing the rearrangement move

+ Here is the call graph for this function:

int pllRearrangeRollback ( pllInstance tr,
partitionList pr 
)

Rollback the last committed rearrangement move.

Perform a rollback (undo) on the last committed rearrangement move.

Parameters
trPLL instance
prList of partitions
Returns
Returns PLL_TRUE is the rollback was successful, otherwise PLL_FALSE (if no rollback was done)

+ Here is the call graph for this function:

void pllRearrangeSearch ( pllInstance tr,
partitionList pr,
int  rearrangeType,
nodeptr  p,
int  mintrav,
int  maxtrav,
pllRearrangeList bestList 
)

Search for rearrangement topologies.

Search for possible rearrangement moves of type rearrangeType in the annular area defined by the minimal resp. maximal radii mintrav resp. maxtrav. If the resulting likelihood is better than the current, try to insert the move specification in bestList, which is a sorted list that holds the rearrange info of the best moves sorted by likelihood (desccending order).

Parameters
trPLL instance
prList of partitions
rearrangeTypeType of rearrangement. Can be PLL_REARRANGE_SPR or PLL_REARRANGE_NNI
pPoint of origin, i.e. where to start searching from
mintravThe minimal radius of the annulus
maxtravThe maximal radius of the annulus
bestListList that holds the details of the best rearrangement moves found
Note
If bestList is not empty, the existing entries will not be altered unless better rearrangement moves (that means yielding better likelihood) are found and the list is full, in which case the entries with the worst likelihood will be thrown away.

+ Here is the call graph for this function:

static void pllRollbackNNI ( pllInstance tr,
partitionList pr,
pllRollbackInfo ri 
)
static

Rollback an NNI move.

Perform a rollback (undo) on the last NNI move.

Parameters
trPLL instance
prList of partitions
riRollback information

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pllRollbackSPR ( pllInstance tr,
partitionList pr,
pllRollbackInfo ri 
)
static

Rollback an SPR move.

Perform a rollback (undo) on the last SPR move.

Parameters
trPLL instance
prList of partitions
riRollback information

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pllSearchNNI ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  mintrav,
int  maxtrav,
pllRearrangeList bestList 
)
static

Compute a list of possible NNI moves.

Iteratively tries all possible NNI moves at each node that is at least mintrav and at most maxtrav nodes far from node p. At each NNI move, the likelihood is tested and if it is higher than the likelihood of an element in the sorted (by likelihood) list bestList, or if there is still empty space in bestList, it is inserted at the corresponding position.

Parameters
trPLL instance
prList of partitions
pNode specifying the point where the NNI will be performed.
mintravMinimum distance from p where the NNI can be tested
maxtravMaximum distance from p where to try NNIs

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static int pllStoreRearrangement ( pllRearrangeList bestList,
pllRearrangeInfo rearr 
)
static

Store a rearrangement move to the list of best rearrangement moves.

Checks if the likelihood yielded by the rearrangement move described in rearr is better than any in the sorted list bestList. If it is, or if there is still space in bestList, the info about the move is inserted in the list.

Parameters
bestListThe list of information about the best rearrangement moves
rearrInfo about the current rearrangement move
Returns
Returns PLL_FALSE if the rearrangement move doesn't make it in the list, otherwise PLL_TRUE

+ Here is the caller graph for this function:

static int pllTestInsertBIG ( pllInstance tr,
partitionList pr,
nodeptr  p,
nodeptr  q,
pllRearrangeList bestList 
)
static

Internal function for testing and saving an SPR move.

Checks the likelihood of the placement of the pruned subtree specified by p to node q. If the likelihood is better than some in the sorted list bestList, or if there is still free space in bestList, then the SPR move is recorded (in bestList)

Parameters
trPLL instance
prList of partitions
pRoot of the subtree that is to be pruned
qWhere to place the pruned subtree (between q and q->back
bestListWhere to store the SPR move
Note
Internal function which is not part of the PLL API and therefore should not be called by the user
Returns

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pllTestNNI ( pllInstance tr,
partitionList pr,
nodeptr  p,
pllRearrangeList bestList 
)
static

Compares NNI likelihoods at a node and store in the rearrangement list.

Compares the two possible NNI moves that can be performed at node p, and if the likelihood improves from the one of the original topology, then it picks the one that yields the highest likelihood and tries to insert it in the list of best rearrangement moves

Parameters
trPLL instance
prList of partitions
bestListRearrangement moves list

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static double pllTestNNILikelihood ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  swapType 
)
static

Return the yielded likelihood of an NNI move, without altering the topology.

This function performs the NNI move of type swapType at node p, optimizes the branch with endpoints p and p->back and evalutes the resulting likelihood. It then restores the topology to the origin and returns the likelihood that the NNI move yielded.

Parameters
trPLL instance
prList of partitions
pWhere to perform the NNI move
swapTypeWhat type of NNI move to perform
Returns
The likelihood yielded from the NNI

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static int pllTestSPR ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  mintrav,
int  maxtrav,
pllRearrangeList bestList 
)
static

Internal function for computing SPR moves.

Compute a list of at most max SPR moves that can be performed by pruning the subtree rooted at node p and testing all possible placements in a radius of at least mintrav nodes and at most maxtrav nodes from p. Note that tr->thoroughInsertion affects the behaviour of the function (see note).

Parameters
trPLL instance
prList of partitions
pNode specifying the root of the pruned subtree, i.e. where to prune.
mintravMinimum distance from p where to try inserting the pruned subtree
maxtravMaximum distance from p where to try inserting the pruned subtree
bestListThe list of best topological rearrangements
Note
This function is not part of the API and should not be called by the user as it is called internally by the API function pllComputeSPR. Also, setting tr->thoroughInsertion affects this function. For each tested SPR the new branch lengths will also be optimized. This computes better likelihoods but also slows down the method considerably.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pllTraverseNNI ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  mintrav,
int  maxtrav,
pllRearrangeList bestList 
)
static

Recursive traversal of the tree structure for testing NNI moves.

Recursively traverses the tree structure and tests all allowed NNI moves in the area specified by mintrav and maxtrav. For more information and details on the function arguments check pllSearchNNI

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void pllTraverseUpdate ( pllInstance tr,
partitionList pr,
nodeptr  p,
nodeptr  q,
int  mintrav,
int  maxtrav,
pllRearrangeList bestList 
)
static

Internal function for recursively traversing a tree and testing a possible subtree insertion.

Recursively traverses the tree rooted at q in the direction of q->next->back and q->next->next->back and at each node tests the placement of the pruned subtree rooted at p by calling the function pllTestInsertBIG, which in turn saves the computed SPR in bestList if a) there is still space in the bestList or b) if the likelihood of the SPR is better than any of the ones in bestList.

Note
This function is not part of the API and should not be called by the user.

+ Here is the call graph for this function:

+ Here is the caller graph for this function: