1 | ;
|
2 |
|
3 |
|
4 | /*
|
5 | trees - a module for trees in gramene
|
6 |
|
7 | */
|
8 | var TreeModel = require('tree-model');
|
9 | var FlatToNested = require('flat-to-nested');
|
10 | var _ = require('lodash');
|
11 | var treemodelExtensions = require('./treemodelExtensions');
|
12 |
|
13 | module.exports = {
|
14 | tree: function (taxonomy) {
|
15 | function cleanUpProperties(taxonomy) {
|
16 | return taxonomy.map(function (taxon) {
|
17 | if (!taxon.is_a) {
|
18 | if (taxon._id !== 1) {
|
19 | throw new Error('unrooted node!');
|
20 | }
|
21 | }
|
22 | if (taxon.hasOwnProperty('property_value')) {
|
23 | taxon.rank = taxon.property_value.replace(/has_rank NCBITaxon:/,'');
|
24 | }
|
25 | return {
|
26 | id: taxon._id,
|
27 | parent: taxon.is_a ? taxon.is_a[0] : undefined,
|
28 | rank: taxon.rank,
|
29 | name: taxon.name,
|
30 | synonyms: taxon.synonym || [],
|
31 | geneCount: taxon.num_genes,
|
32 | reactomePrefix: taxon.reactomePrefix
|
33 | };
|
34 | });
|
35 | }
|
36 |
|
37 | function createTree(nestedTaxa) {
|
38 | function childNodeNameLexComparator(a, b) {
|
39 | return a.name > b.name ? 1 : -1;
|
40 | }
|
41 | function childNodeGeneCountComparator(a, b) {
|
42 | return a.geneCount < b.geneCount ? 1 : -1;
|
43 | }
|
44 |
|
45 | return new TreeModel({modelComparatorFn: childNodeGeneCountComparator}).parse(nestedTaxa);
|
46 | }
|
47 |
|
48 | function compressTreePaths(tree) {
|
49 | tree.all(function (node) {
|
50 | return !node.isRoot() && node.children.length === 1;
|
51 | }).forEach(function (node) {
|
52 | var parent = node.parent
|
53 | , child = node.children[0];
|
54 |
|
55 | parent.addChild(child);
|
56 | node.drop();
|
57 |
|
58 | // maintain the link from the compressed node to the parent
|
59 | // (this is deleted in call to node.drop())
|
60 | node.parent = parent;
|
61 | node.compressed = true;
|
62 |
|
63 | // Add compressed nodes to child and not parent
|
64 | if (!child.compressedNodes) {
|
65 | child.compressedNodes = [];
|
66 | }
|
67 | child.compressedNodes.push(node);
|
68 | if (node.compressedNodes) {
|
69 | child.compressedNodes = node.compressedNodes.concat(child.compressedNodes);
|
70 | delete node.compressedNodes;
|
71 | }
|
72 | });
|
73 | }
|
74 |
|
75 | //function decorateTree(tree) {
|
76 | // tree.lca = function lowestCommonAncestor(nodes) {
|
77 | // var parentNodesInCommon = _.chain(nodes)
|
78 | // .map(function (node) {
|
79 | // return node.getPath();
|
80 | // })
|
81 | // .reduce(function (acc, nextPath) {
|
82 | // return _.intersection(acc, nextPath)
|
83 | // })
|
84 | // .value();
|
85 | // return parentNodesInCommon.pop();
|
86 | // };
|
87 | //
|
88 | // tree.pathBetween = function pathBetweenNodes(from, to) {
|
89 | //
|
90 | // var lca, fromPath, toPath, fromLcaIdx, toLcaIdx, pathBetween;
|
91 | //
|
92 | // // find the lowest commen ancestor
|
93 | // lca = tree.lca([from, to]);
|
94 | //
|
95 | // // get the full path from -> root, and reverse it
|
96 | // fromPath = _(from.getPath().reverse());
|
97 | //
|
98 | // // get the full path to -> root
|
99 | // toPath = _(to.getPath());
|
100 | //
|
101 | // // find the index of lca in fromPath and toPath
|
102 | // fromLcaIdx = fromPath.findIndex(lca);
|
103 | // toLcaIdx = toPath.findIndex(lca);
|
104 | //
|
105 | // // slice and combine the arrays to get the path between
|
106 | // pathBetween = fromPath.slice(0, fromLcaIdx).concat(toPath.slice(toLcaIdx).value());
|
107 | //
|
108 | // return pathBetween.value();
|
109 | // };
|
110 | //}
|
111 | //
|
112 | //function addPrototypeDecorations(tree) {
|
113 | // var prototree = Object.getPrototypeOf(tree);
|
114 | //
|
115 | // prototree.depth = function calculateEffectiveNodeDepth(includeCompressedNodes) {
|
116 | // var path = this.getPath()
|
117 | // , depth = path.length - 1
|
118 | // , compressedDepth;
|
119 | //
|
120 | // if(includeCompressedNodes) {
|
121 | // compressedDepth = _.reduce(path, function (acc, n) {
|
122 | // return acc + (n.compressedNodes ? n.compressedNodes.length : 0);
|
123 | // }, 0);
|
124 | // depth += compressedDepth;
|
125 | // }
|
126 | //
|
127 | // return depth;
|
128 | // };
|
129 | //
|
130 | // prototree.pathTo = function(to) {
|
131 | // return tree.pathBetween(this, to);
|
132 | // };
|
133 | //
|
134 | // prototree.leafNodes = function findAllLeafNodes() {
|
135 | // return this.all(function (node) { return !node.hasChildren(); });
|
136 | // };
|
137 | //
|
138 | // prototree.lcaWith = function(otherNodes) {
|
139 | // var nodes = _.clone(otherNodes);
|
140 | // nodes.push(this);
|
141 | // return tree.lca(nodes);
|
142 | // }
|
143 | //}
|
144 | //
|
145 | //function indexTree(tree, attrs) {
|
146 | // tree.indices = _.chain(attrs)
|
147 | // .map(function (attr) {
|
148 | // var result = {_attr: attr};
|
149 | // tree.walk(function (node) {
|
150 | // result[node.model[attr]] = node;
|
151 | // });
|
152 | // return result;
|
153 | // })
|
154 | // .indexBy('_attr')
|
155 | // .value();
|
156 | //}
|
157 |
|
158 | var taxa
|
159 | , nestedTaxa
|
160 | , tree;
|
161 |
|
162 | taxa = cleanUpProperties(taxonomy);
|
163 | nestedTaxa = new FlatToNested().convert(taxa);
|
164 | tree = createTree(nestedTaxa);
|
165 | treemodelExtensions.indexTree(tree, ['id', 'name']);
|
166 | compressTreePaths(tree);
|
167 | treemodelExtensions.decorateTree(tree);
|
168 | treemodelExtensions.addPrototypeDecorations(tree);
|
169 |
|
170 | return tree;
|
171 | }
|
172 | }; |
\ | No newline at end of file |