binaries/src/GLProbs-1.0/MSAGuideTree.h

   1 /***********************************************
   2  * # Copyright 2009-2010. Liu Yongchao
   3  * # Contact: Liu Yongchao, School of Computer Engineering,
   4  * #                     Nanyang Technological University.
   5  * # Emails:     liuy0039@ntu.edu.sg; nkcslyc@hotmail.com
   6  * #
   7  * # GPL version 3.0 applies.
   8  * #
   9  * ************************************************/
  10
  11 #ifndef _MSA_GUIDE_TREE_H
  12 #define _MSA_GUIDE_TREE_H
  13 #include "MSADef.h"
  14 #include "MSA.h"
  15
  16 #include "SafeVector.h"
  17 #include "MultiSequence.h"
  18 #include "ScoreType.h"
  19 #include "ProbabilisticModel.h"
  20 #include "SparseMatrix.h"
  21
  22 class MSA;
  23 struct ValidNode {
  24         ValidNode* prev;
  25         ValidNode* next;
  26         int n;                          //the index in the distance matrix
  27         int node;                       //the index in the tree node entries
  28 };
  29
  30 struct TreeNode {
  31         struct TreeNode *left;                  //the pointer to its left child
  32         struct TreeNode *right;                 //the pointer to its right child
  33         struct TreeNode *parent;                //the pointer to its parent
  34         int leftIdx;                                    //the index of the left child
  35         int rightIdx;                                   //the index of the right child
  36         int parentIdx;                                  //the index of its parent
  37         int idx;                                                //the index of itself
  38         float dist;                                             //the distance to its parent
  39         int leaf;                                               //whether it is a leaf node or not
  40         int order;                      //the number of generations dating back to its ancestor
  41         int depth;                                              //the depth of the node
  42 };
  43 struct AlignmentOrder {
  44         int nodeDepth;                  //the depth of the internal node
  45         int leftOrder;                  //the order number of the right child
  46         int rightOrder;                 //the order number of the left child
  47         int* leftLeafs;                 //the indices of leafs in the left subtree
  48         int leftNum;                    //the number of leafs in the left subtree
  49         int* rightLeafs;                        //the indices of leafs in the right subtree
  50         int rightNum;                   //the number of leafs in the right substree
  51 };
  52
  53 class MSAGuideTree {
  54 public:
  55         MSAGuideTree(MSA* msa, VVF& distMatrix, int numSeqs);
  56         virtual ~MSAGuideTree() = 0;    //abstract class
  57
  58         //get the tree nodes
  59         TreeNode* getNodes();
  60         //get the leaf nodes
  61         TreeNode* getLeafs();
  62         //get the number of nodes;
  63         int getNodesNum();
  64         //get the number of leaf nodes
  65         int getLeafsNum();
  66         //get the root of the tree
  67         TreeNode* getRoot() {
  68                 return this->root;
  69         }
  70         //get the alignment orders
  71         AlignmentOrder* getAlignOrders();
  72         int getAlignOrdersNum();
  73         //construct the alignment orders
  74         void createAlignmentOrders();
  75
  76         //construct the guide tree
  77         virtual void create();
  78         //calculate the sequence weights
  79         virtual void getSeqsWeights();
  80
  81         /**********DEBUGING****************/
  82         //display the tree
  83         void displayTree();
  84         //display the alignment orders
  85         void displayAlignmentOrders();
  86
  87 protected:
  88         //join two nodes
  89         void connectNodes(TreeNode* parent, int parentIdx, TreeNode* leftChild,
  90                         float leftDist, TreeNode* rightChild, float rightDist);
  91         //release the alignment orders vector
  92         void releaseAlignmentOrders();
  93         //recursive implemenation of constructing the alignment orders
  94         int recursiveCreateAlignmentOrders(TreeNode* subRoot, int* subLeafs,
  95                         int& subLeafsNum, int nodeDepth);
  96
  97         //system configurations
  98         MSA* msa;
  99         VVF* distMatrix;
 100         int numSeqs;
 101         int* seqsWeights;
 102
 103         //all the tree nodes
 104         TreeNode* nodes;
 105         int nodesNum;
 106         int nodesSize;
 107         //the root tree node
 108         TreeNode* root;
 109         //leaf node
 110         TreeNode* leafs;
 111         int leafsNum;
 112
 113         //alignment order
 114         AlignmentOrder* alignOrders;
 115         int alignOrdersNum;
 116         int alignOrdersSize;
 117 };
 118 #endif
 119