source: tags/arb-6.0/CONSENSUS_TREE/CT_dtree.cxx

Last change on this file was 11401, checked in by westram, 10 years ago
  • reintegrates 'tree' into 'trunk':
    • consensus trees:
      • support for merging partial trees ("worked" before, but results were crap; implements #65)
      • generated trees are automatically re-rooted and -ordered
      • always list source trees in consensus-tree-comment; show info about partial trees
      • fixed progress bar
    • made GBT_TREE a base class of other tree classes (implements #31)
    • save tree properties in properties (not in DB)
    • new functions 'Remove zombies/marked from ALL trees'
    • tree load/save: layout fixes
    • unit tests
      • added tests for basic tree modifications (PARSIMONY)
    • performance:
      • compute_tree updates tree information in one traversal
      • tree generators are now capable to generate any type of tree (w/o needing to copy it once)
    • bugfixes:
      • NNI (of marked species) was also always performed for colored species
      • centered beautify-order is stable now
      • improved 'search optimal root'
  • adds:
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.6 KB
Line 
1// ============================================================= //
2//                                                               //
3//   File      : CT_dtree.cxx                                    //
4//   Purpose   :                                                 //
5//                                                               //
6//   Institute of Microbiology (Technical University Munich)     //
7//   http://www.arb-home.de/                                     //
8//                                                               //
9// ============================================================= //
10
11#include "CT_hash.hxx"
12#include "CT_ctree.hxx"
13
14PART *ConsensusTree::deconstruct_full_subtree(const GBT_TREE *tree, const GBT_LEN& len, const double& weight) {
15    /*! deconstruct GBT_TREE and register found partitions.
16     * @param len length of branch towards subtree 'tree'
17     * @param weight summarized for indentical branches (from different trees)
18     */
19
20    arb_assert(tree->father);
21
22    PART *ptree = NULL;
23    if (tree->is_leaf) {
24        ptree = create_tree_PART(tree, weight);
25    }
26    else {
27        PART *p1 = deconstruct_full_subtree(tree->leftson, tree->leftlen, weight);
28        PART *p2 = deconstruct_full_subtree(tree->rightson, tree->rightlen, weight);
29
30        arb_assert(p1->disjunct_from(p2));
31
32        ptree = p1->clone();
33        ptree->add_members_from(p2);
34
35        registry->put_part_from_complete_tree(p1);
36        registry->put_part_from_complete_tree(p2);
37    }
38    ptree->set_len(len);
39    inc_insert_progress();
40    return ptree;
41}
42
43void ConsensusTree::deconstruct_full_rootnode(const GBT_TREE *tree, const double& weight) {
44    /*! deconstruct GBT_TREE and register found partitions.
45     * @param weight summarized for indentical branches (from different trees)
46     */
47
48    arb_assert(!tree->father);
49    arb_assert(!tree->is_leaf);
50
51    double root_length = (tree->leftlen + tree->rightlen);
52
53    PART *p1 = deconstruct_full_subtree(tree->leftson, root_length, weight);
54    PART *p2 = deconstruct_full_subtree(tree->rightson, root_length, weight);
55
56    arb_assert(p1->disjunct_from(p2));
57
58    // add only one of the partition p1 and p2 (they both represent the root-edge)
59    registry->put_part_from_complete_tree(p1);
60    delete p2;
61
62    inc_insert_progress();
63}
64
65PART *ConsensusTree::deconstruct_partial_subtree(const GBT_TREE *tree, const GBT_LEN& len, const double& weight, const PART *partialTree) {
66    /*! deconstruct partial GBT_TREE
67     *
68     * similar to deconstruct_full_subtree(),
69     * but the set of missing species is added at each branch.
70     */
71
72    arb_assert(tree->father);
73
74    PART *ptree = NULL;
75    if (tree->is_leaf) {
76        ptree = create_tree_PART(tree, weight);
77    }
78    else {
79        PART *p1 = deconstruct_partial_subtree(tree->leftson, tree->leftlen, weight, partialTree);
80        PART *p2 = deconstruct_partial_subtree(tree->rightson, tree->rightlen, weight, partialTree);
81
82        arb_assert(p1->disjunct_from(p2));
83
84        ptree = p1->clone();
85        ptree->add_members_from(p2);
86
87        registry->put_part_from_partial_tree(p1, partialTree);
88        registry->put_part_from_partial_tree(p2, partialTree);
89    }
90    ptree->set_len(len);
91    inc_insert_progress();
92    return ptree;
93}
94
95void ConsensusTree::deconstruct_partial_rootnode(const GBT_TREE *tree, const double& weight, const PART *partialTree) {
96    /*! deconstruct partial GBT_TREE
97     *
98     * similar to deconstruct_full_rootnode(),
99     * but the set of missing species is added at each branch.
100     */
101
102    arb_assert(!tree->father);
103    arb_assert(!tree->is_leaf);
104
105    double root_length = (tree->leftlen + tree->rightlen);
106
107    PART *p1 = deconstruct_partial_subtree(tree->leftson, root_length, weight, partialTree);
108    PART *p2 = deconstruct_partial_subtree(tree->rightson, root_length, weight, partialTree);
109
110    arb_assert(p1->disjunct_from(p2));
111
112    p2->add_members_from(p1); // in p2 we collect the whole partialTree
113    registry->put_part_from_partial_tree(p1, partialTree); // because we are at root edge, we only insert one partition
114
115    arb_assert(p2->equals(partialTree));
116
117    arb_assert(is_similar(p2->get_weight(), weight, 0.01));
118    registry->put_artificial_part(p2);
119    inc_insert_progress();
120}
121
122void ConsensusTree::add_tree_to_PART(const GBT_TREE *tree, PART& part) const {
123    if (tree->is_leaf) {
124        part.setbit(get_species_index(tree->name));
125    }
126    else {
127        add_tree_to_PART(tree->leftson, part);
128        add_tree_to_PART(tree->rightson, part);
129    }
130}
131
132PART *ConsensusTree::create_tree_PART(const GBT_TREE *tree, const double& weight) const {
133    PART *part = new PART(size, weight);
134    if (part) add_tree_to_PART(tree, *part);
135    return part;
136}
137
Note: See TracBrowser for help on using the repository browser.