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...  
pllRearrangeList *  pllCreateRearrangeList (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 
Collection of routines for performing likelihood computation and branch optimization.
Detailed description to appear soon.
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.
tr  PLL instance 
pr  List of partitions 
p  Leaf node of one tree component 
q  Endpoint node of the edge to test the insertion 
mintrav  Minimum radius around q to test the insertion 
maxtrav  Maximum radius around q to test the insertion\ 

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.
tr  The library instance 

static 
Deallocate the contents of an infoList.
Deallocate the contents of a given infoList by freeing the memory used by its bestInfo list structure.
iList  The infoList to be used. 
nniMove getBestNNIForBran  (  pllInstance *  tr, 
partitionList *  pr,  
nodeptr  p,  
double  curLH  
) 
Gets the best NNI move for a branch.
tr  PLL instance 
pr  List of partitions 
p  Node to use as origin for performing NNI 
curLH  The current likelihood 

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.
iList  The given infoList. 
n  Number 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.
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.
node  The given node 
likelihood  The given likelihood 
iList  The given infoList where the record will possibly be appended. 
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.
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.
tr  The library instance 
p  The node around which to optimize the edges 
maxtimes  Number of optimization rounds to perform 
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.
tr  PLL instance 
p  Node to use as origin for performing NNI 
swap  Which node to use for the NNI move. PLL_NNI_P_NEXT uses node p>next while PLL_NNI_P_NEXTNEXT uses p>next>next 
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.
tr  PLL instance 
pr  List of partitions 
estimateModel  Determine wheter the model parameters should be optimized 
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
tr  The PLL instance 
pr  List of partitions 
maxSmoothIterations  Number of times to optimize branch lengths 
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.
tr  PLL instancve 
pr  List of partitions 
p  Node from which to start the SPR moves testing 
mintrav  Minimum distance from p where to start testing SPRs 
maxtrav  Maximum distance from p where to test SPRs 
q1>tip
q2>tip
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.
tr  The library instance. 
p  Node to start branch optimization from. 
maxtimes  Number of times to perform branch optimization. 
region  The allwed node distance from for which to still perform branch optimization. 
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.
tr  The library instance 
p  The node at which the tree should be decomposed into two components. 
numBranches  Number of branches per partition 
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.
tr  The library instance 
p  The node at which the tree should be decomposed into two components. 

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.
iList  The given infoList. 
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
tr  The library instance 
pr  Partition list 
p  Endpoint of branches to be optimized 
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.
tr  The library instance. 
p  Node to start branch optimization from. 
region  The allowed node distance from for which to still perform branch optimization. 
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.
tr  The library instance 
maxtimes  Number of optimization rounds to perform 
double treeOptimizeRapid  (  pllInstance *  tr, 
partitionList *  pr,  
int  mintrav,  
int  maxtrav,  
bestlist *  bt,  
infoList *  iList  
) 
Perform an SPR move?
tr  PLL instance 
pr  List of partitions 
mintrav  
maxtrav  
adef  
bt  
iList 
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.
tr  The library instance 
pr  Partition list 
p  Endpoints of branch to be optimized 

static 
Write a checkpoint.
Is checkpoint enabled?

static 
Write tree to file.
Serialize tree to a file.
double accumulatedTime 
Accumulated time for checkpointing
char binaryCheckpointName[1024] 
Binary checkpointing file
double masterTime 
Needed for checkpointing
char seq_file[1024] 
Checkpointing related file