Functions | Variables
searchAlgo.c File Reference

Collection of routines for performing likelihood computation and branch optimization. More...

Functions

double treeOptimizeRapid (pllInstance *tr, partitionList *pr, int mintrav, int maxtrav, bestlist *bt, infoList *iList)
 Perform an SPR move? More...
 
nniMove getBestNNIForBran (pllInstance *tr, partitionList *pr, nodeptr p, double curLH)
 Gets the best NNI move for a branch. More...
 
void evalNNIForSubtree (pllInstance *tr, partitionList *pr, nodeptr p, nniMove *nniList, int *cnt, int *cnt_nni, double curLH)
 ??? Not sure
 
static int cmp_nni (const void *nni1, const void *nni2)
 Compares 2 NNI moves.
 
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 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 int pllTestSPR (pllInstance *tr, partitionList *pr, nodeptr p, int mintrav, int maxtrav, pllRearrangeList *bestList)
 Internal function for computing SPR 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 pllRollbackNNI (pllInstance *tr, partitionList *pr, pllRollbackInfo *ri)
 Rollback an NNI move. More...
 
static void pllRollbackSPR (pllInstance *tr, partitionList *pr, pllRollbackInfo *ri)
 Rollback an SPR move. More...
 
boolean initrav (pllInstance *tr, partitionList *pr, nodeptr p)
 
void update (pllInstance *tr, partitionList *pr, nodeptr p)
 Optimize the length of a specific branch. More...
 
void smooth (pllInstance *tr, partitionList *pr, nodeptr p)
 Branch length optimization of subtree. More...
 
static boolean allSmoothed (pllInstance *tr, int numBranches)
 Check whether the branches in all partitions have been optimized. More...
 
void smoothTree (pllInstance *tr, partitionList *pr, int maxtimes)
 Optimize all branch lenghts of a tree. More...
 
void localSmooth (pllInstance *tr, partitionList *pr, nodeptr p, int maxtimes)
 Optimize the branch length of edges around a specific node. More...
 
static void resetInfoList (infoList *iList)
 Reset an infoList. More...
 
static void initInfoList (infoList *iList, int n)
 Initialize an infoList. More...
 
static void freeInfoList (infoList *iList)
 Deallocate the contents of an infoList. More...
 
static void insertInfoList (nodeptr node, double likelihood, infoList *iList)
 Insert a record in an infoList. More...
 
void smoothRegion (pllInstance *tr, partitionList *pr, nodeptr p, int region)
 Optimize branch lengths of region. More...
 
void regionalSmooth (pllInstance *tr, partitionList *pr, nodeptr p, int maxtimes, int region)
 Wrapper function for optimizing the branch length of a region maxtimes times. More...
 
nodeptr removeNodeBIG (pllInstance *tr, partitionList *pr, nodeptr p, int numBranches)
 Split the tree into two components and optimize new branch length. More...
 
nodeptr removeNodeRestoreBIG (pllInstance *tr, partitionList *pr, nodeptr p)
 Split the tree into two components and recompute likelihood. More...
 
boolean insertBIG (pllInstance *tr, partitionList *pr, nodeptr p, nodeptr q)
 Connect two disconnected tree components. More...
 
boolean insertRestoreBIG (pllInstance *tr, partitionList *pr, nodeptr p, nodeptr q)
 Connect two disconnected tree components without optimizing branch lengths. More...
 
static void restoreTopologyOnly (pllInstance *tr, bestlist *bt, int numBranches)
 
boolean testInsertBIG (pllInstance *tr, partitionList *pr, nodeptr p, nodeptr q)
 Test the.
 
void addTraverseBIG (pllInstance *tr, partitionList *pr, nodeptr p, nodeptr q, int mintrav, int maxtrav)
 Recursively traverse tree and test insertion. More...
 
int rearrangeBIG (pllInstance *tr, partitionList *pr, nodeptr p, int mintrav, int maxtrav)
 Compute the best SPR movement. More...
 
boolean testInsertRestoreBIG (pllInstance *tr, partitionList *pr, nodeptr p, nodeptr q)
 
void restoreTreeFast (pllInstance *tr, partitionList *pr)
 
static void myfwrite (const void *ptr, size_t size, size_t nmemb, FILE *stream)
 
static void myfread (void *ptr, size_t size, size_t nmemb, FILE *stream)
 
static void writeTree (pllInstance *tr, FILE *f)
 Write tree to file. More...
 
static void writeCheckpoint (pllInstance *tr, partitionList *pr, int state)
 Write a checkpoint. More...
 
static void readTree (pllInstance *tr, partitionList *pr, FILE *f)
 
static void readCheckpoint (pllInstance *tr, partitionList *pr)
 
static void restoreTreeDataValuesFromCheckpoint (pllInstance *tr)
 
void restart (pllInstance *tr, partitionList *pr)
 
void pllTreeEvaluate (pllInstance *tr, partitionList *pr, int maxSmoothIterations)
 Optimize branch lenghts and evaluate likelihood of topology. More...
 
int NNI (pllInstance *tr, nodeptr p, int swap)
 Perform an NNI move. More...
 
int pllNniSearch (pllInstance *tr, partitionList *pr, int estimateModel)
 Perform an NNI search. More...
 
pllRearrangeListpllCreateRearrangeList (int max)
 Create a list for storing topology rearrangements. More...
 
void pllDestroyRearrangeList (pllRearrangeList **bestList)
 Deallocator for topology rearrangements list. 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...
 
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...
 

Variables

double accumulatedTime
 
char seq_file [1024]
 
double masterTime
 
partitionLengths pLengths [PLL_MAX_MODEL]
 
char binaryCheckpointName [1024]
 
char binaryCheckpointInputName [1024]
 
int ckpCount = 0
 

Detailed Description

Collection of routines for performing likelihood computation and branch optimization.

Detailed description to appear soon.

Function Documentation

void addTraverseBIG ( pllInstance tr,
partitionList pr,
nodeptr  p,
nodeptr  q,
int  mintrav,
int  maxtrav 
)

Recursively traverse tree and test insertion.

Recursively traverses the tree structure starting from node q and tests the insertion of the component specified by leaf p at the edge between q and q->back.

Parameters
trPLL instance
prList of partitions
pLeaf node of one tree component
qEndpoint node of the edge to test the insertion
mintravMinimum radius around q to test the insertion
maxtravMaximum radius around q to test the insertion\

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static boolean allSmoothed ( pllInstance tr,
int  numBranches 
)
static

Check whether the branches in all partitions have been optimized.

Check if all branches in all partitions have reached the threshold for optimization. If at least one branch can be optimized further return PLL_FALSE.

Parameters
trThe library instance
Returns
If at least one branch can be further optimized return PLL_FALSE, otherwise PLL_TRUE.

+ Here is the caller graph for this function:

static void freeInfoList ( infoList iList)
static

Deallocate the contents of an infoList.

Deallocate the contents of a given infoList by freeing the memory used by its bestInfo list structure.

Parameters
iListThe infoList to be used.
nniMove getBestNNIForBran ( pllInstance tr,
partitionList pr,
nodeptr  p,
double  curLH 
)

Gets the best NNI move for a branch.

Parameters
trPLL instance
prList of partitions
pNode to use as origin for performing NNI
curLHThe current likelihood
Returns
The best NNI move

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void initInfoList ( infoList iList,
int  n 
)
static

Initialize an infoList.

Initialize an infoList by creating a bestInfo list structure of n elements and setting the attributes node and likelihood of each element of the bestInfo list structure to NULL and PLL_UNLIKELY, respectively.

Parameters
iListThe given infoList.
nNumber of elements to be created in the bestInfo list.
boolean insertBIG ( pllInstance tr,
partitionList pr,
nodeptr  p,
nodeptr  q 
)

Connect two disconnected tree components.

Connect two disconnected components by specifying an internal edge from one component and a leaf from the other component. The internal edge e is the edge between q and q->back. The leaf is specified by p. Edge e is removed and two new edges are created. The first one is an edge between p->next and q, and the second one is between p->next->next and q->back. The new likelihood vector for node p is computed.

Note
The function makes use of the thoroughInsertion flag
Todo:
What is tr->lzi ? What is thorough insertion? Why do we optimize branch lengths that will be removed? Add explanation
pll.png
The diagram shows in blue colors the new edges that are created and in red the edge that is removed

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void insertInfoList ( nodeptr  node,
double  likelihood,
infoList iList 
)
static

Insert a record in an infoList.

Insert the pair likelihood and into list iList only if there already exists a pair in iList whose likelihood attribute is smaller than the given likelihood. The insertion is done by replacing the smallest likelihood pair with the new pair.

Parameters
nodeThe given node
likelihoodThe given likelihood
iListThe given infoList where the record will possibly be appended.

+ Here is the caller graph for this function:

boolean insertRestoreBIG ( pllInstance tr,
partitionList pr,
nodeptr  p,
nodeptr  q 
)

Connect two disconnected tree components without optimizing branch lengths.

Connect two disconnected components by specifying an internal edge from one component and a leaf from the other component. The internal edge e is the edge between q and q->back. The leaf is specified by p. Edge e is removed and two new edges are created. The first one is an edge between p->next and q, and the second one is between p->next->next and q->back. The new likelihood vector for node p is computed.

Note
The function makes use of the thoroughInsertion flag
Todo:
What is the difference between this and insertBIG?

+ Here is the call graph for this function:

void localSmooth ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  maxtimes 
)

Optimize the branch length of edges around a specific node.

Optimize maxtimes the branch length of all (3) edges around a given node p of the tree of library instance tr.

Parameters
trThe library instance
pThe node around which to optimize the edges
maxtimesNumber of optimization rounds to perform

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

int NNI ( pllInstance tr,
nodeptr  p,
int  swap 
)

Perform an NNI move.

Modify the tree topology of instance tr by performing an NNI (Neighbour Neighbor Interchange) move at node p. Let q be p->back. If swap is set to PLL_NNI_P_NEXT then the subtrees rooted at p->next->back and q->next->back will be swapped. Otherwise, if swap is set to PLL_NNI_P_NEXTNEXT then the subtrees rooted at p->next->next->back and q->next->back are swapped. For clarity, see the illustration.

Parameters
trPLL instance
pNode to use as origin for performing NNI
swapWhich node to use for the NNI move. PLL_NNI_P_NEXT uses node p->next while PLL_NNI_P_NEXTNEXT uses p->next->next
Returns
In case of success PLL_TRUE, otherwise PLL_FALSE
Todo:
Started error checking here. Instead of checking the errors in the specified way, implement a variadic function where we pass the results of each check and the error code we want to assign if there is at least one negative result
nni.png
In case swap is set to PLL_NNI_P_NEXT then the dashed red edge between p and r is removed and the blue edges are created. If swap is set to PLL_INIT_P_NEXTNEXT then the dashed red edge between p and s is removed and the green edges are created. In both cases the black dashed edge is removed

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

int pllNniSearch ( pllInstance tr,
partitionList pr,
int  estimateModel 
)

Perform an NNI search.

Modify the tree topology of instance and model parameters tr by performing a NNI (Neighbour Neighbor Interchange) moves p.

Parameters
trPLL instance
prList of partitions
estimateModelDetermine wheter the model parameters should be optimized
Returns
In case of success PLL_TRUE, otherwise PLL_FALSE

+ Here is the call graph for this function:

void pllTreeEvaluate ( pllInstance tr,
partitionList pr,
int  maxSmoothIterations 
)

Optimize branch lenghts and evaluate likelihood of topology.

Optimize the branch lengths maxSmoothIterations times and evaluate the likelihood of tree. The resulting likelihood is placed in tr->likelihood

Parameters
trThe PLL instance
prList of partitions
maxSmoothIterationsNumber of times to optimize branch lengths

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

int rearrangeBIG ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  mintrav,
int  maxtrav 
)

Compute the best SPR movement.

Compute all SPR moves starting from p in the space defined by mintrav and maxtrav and store the best in the tr structure.

Parameters
trPLL instancve
prList of partitions
pNode from which to start the SPR moves testing
mintravMinimum distance from p where to start testing SPRs
maxtravMaximum distance from p where to test SPRs
Returns
0,1 or PLL_BADREAR
Todo:
fix the return value

q1->tip

q2->tip

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void regionalSmooth ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  maxtimes,
int  region 
)

Wrapper function for optimizing the branch length of a region maxtimes times.

Optimize the branch lengths of a specific region maxtimes times. The branch optimization starts at a given node p and is carried out in all nodes with distance upto region from p.

Parameters
trThe library instance.
pNode to start branch optimization from.
maxtimesNumber of times to perform branch optimization.
regionThe allwed node distance from for which to still perform branch optimization.
Todo:
In the previous version (before the model-sep merge) the loops were controlled by tr->numBranches, and now they are controlled by a constant PLL_NUM_BRANCHES. What is right?

+ Here is the call graph for this function:

nodeptr removeNodeBIG ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  numBranches 
)

Split the tree into two components and optimize new branch length.

Split the tree into two components. The disconnection point is node p. First, a branch length is computed for the newly created branch between nodes p->next->back and p->next->next->back and then the two nodes are connected (hookup). Disconnection is done by setting p->next->next->back and p->next->back to NULL.

Parameters
trThe library instance
pThe node at which the tree should be decomposed into two components.
numBranchesNumber of branches per partition
Returns
Node from the disconnected component
Todo:
Why do we return this node?
removeBIG.png
The diagram shows in blue color the new edge that is created and in red the edges that are removed

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

nodeptr removeNodeRestoreBIG ( pllInstance tr,
partitionList pr,
nodeptr  p 
)

Split the tree into two components and recompute likelihood.

Split the tree into two component. The disconnection point is node p. Set the branch length of the new node between p->next->back and p->next->next->back to tr->currentZQR and then decompose the tree into two components by setting p->next->back and p->next->next->back to NULL.

Parameters
trThe library instance
pThe node at which the tree should be decomposed into two components.
Returns
q the node after p
Todo:
Why do we return this node? Why do we set to tr->currentZQR and not compute new optimized length? What is tr->currentZQR?

+ Here is the call graph for this function:

static void resetInfoList ( infoList iList)
static

Reset an infoList.

Resets an infoList by setting elements node and likelihood of each element of the bestInfo list structure to NULL and PLL_UNLIKELY, respectively.

Parameters
iListThe given infoList.

+ Here is the caller graph for this function:

void smooth ( pllInstance tr,
partitionList pr,
nodeptr  p 
)

Branch length optimization of subtree.

Optimize the length of branch connected by p and p->back, and the lengths of all branches in the subtrees rooted at p->next and p->next->next

Parameters
trThe library instance
prPartition list
pEndpoint of branches to be optimized

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void smoothRegion ( pllInstance tr,
partitionList pr,
nodeptr  p,
int  region 
)

Optimize branch lengths of region.

Optimize the branch lenghts of only a specific region. The branch optimization starts at a node p and is carried out in all nodes with distance upto region edges from p.

Parameters
trThe library instance.
pNode to start branch optimization from.
regionThe allowed node distance from for which to still perform branch optimization.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void smoothTree ( pllInstance tr,
partitionList pr,
int  maxtimes 
)

Optimize all branch lenghts of a tree.

Perform maxtimes rounds of branch length optimization by running smooth() on all neighbour nodes of node tr->start.

Parameters
trThe library instance
maxtimesNumber of optimization rounds to perform

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

double treeOptimizeRapid ( pllInstance tr,
partitionList pr,
int  mintrav,
int  maxtrav,
bestlist bt,
infoList iList 
)

Perform an SPR move?

Parameters
trPLL instance
prList of partitions
mintrav
maxtrav
adef
bt
iList

+ Here is the call graph for this function:

void update ( pllInstance tr,
partitionList pr,
nodeptr  p 
)

Optimize the length of a specific branch.

Optimize the length of the branch connecting p and p->back for each partition (tr->numBranches) in library instance tr.

Parameters
trThe library instance
prPartition list
pEndpoints of branch to be optimized

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void writeCheckpoint ( pllInstance tr,
partitionList pr,
int  state 
)
static

Write a checkpoint.

Is checkpoint enabled?

Todo:
fill this up

+ Here is the call graph for this function:

static void writeTree ( pllInstance tr,
FILE *  f 
)
static

Write tree to file.

Serialize tree to a file.

Todo:
Document this

+ Here is the caller graph for this function:

Variable Documentation

double accumulatedTime

Accumulated time for checkpointing

char binaryCheckpointName[1024]

Binary checkpointing file

double masterTime

Needed for checkpointing

char seq_file[1024]

Checkpointing related file