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
7 * # GPL version 3.0 applies.
9 * ************************************************/
11 #ifndef _MSA_GUIDE_TREE_H
12 #define _MSA_GUIDE_TREE_H
16 #include "SafeVector.h"
17 #include "MultiSequence.h"
18 #include "ScoreType.h"
19 #include "ProbabilisticModel.h"
20 #include "SparseMatrix.h"
26 int n; //the index in the distance matrix
27 int node; //the index in the tree node entries
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
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
55 MSAGuideTree(MSA* msa, VVF& distMatrix, int numSeqs);
56 virtual ~MSAGuideTree() = 0; //abstract class
62 //get the number of nodes;
64 //get the number of leaf nodes
66 //get the root of the tree
70 //get the alignment orders
71 AlignmentOrder* getAlignOrders();
72 int getAlignOrdersNum();
73 //construct the alignment orders
74 void createAlignmentOrders();
76 //construct the guide tree
77 virtual void create();
78 //calculate the sequence weights
79 virtual void getSeqsWeights();
81 /**********DEBUGING****************/
84 //display the alignment orders
85 void displayAlignmentOrders();
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);
97 //system configurations
114 AlignmentOrder* alignOrders;