1from __future__ import absolute_import 2from __future__ import print_function 3import unittest 4import random 5import itertools 6import json 7 8import sys 9from six.moves import range 10 11from .. import Tree, PhyloTree, TreeNode 12from ..coretype.tree import TreeError 13from ..parser.newick import NewickError 14from .datasets import * 15 16class Test_Coretype_Tree(unittest.TestCase): 17 """ Tests tree basics. """ 18 def test_read_write_exceptions(self): 19 20 def wrong_dist(): 21 t = Tree() 22 t.dist = '1a' 23 24 def wrong_support(): 25 t = Tree() 26 t.support = '1a' 27 28 def wrong_up(): 29 t = Tree() 30 t.up = 'Something' 31 32 def wrong_children(): 33 t = Tree() 34 t.children = 'Something' 35 36 self.assertRaises(TreeError, wrong_dist) 37 self.assertRaises(TreeError, wrong_support) 38 self.assertRaises(TreeError, wrong_up) 39 self.assertRaises(TreeError, wrong_children) 40 41 def test_add_remove_features(self): 42 #The features concept will probably change in future versions. It is 43 #very inefficient in larg trees. 44 t = Tree() 45 t.add_features(testf1=1, testf2="1", testf3=[1]) 46 t.add_feature('testf4', set([1])) 47 self.assertEqual(t.testf1, 1) 48 self.assertEqual(t.testf2, "1") 49 self.assertEqual(t.testf3, [1]) 50 self.assertEqual(t.testf4, set([1])) 51 52 t.del_feature('testf4') 53 self.assertTrue('testf4' not in t.features) 54 55 def test_tree_read_and_write(self): 56 """ Tests newick support """ 57 # Read and write newick tree from file (and support for NHX 58 # format): newick parser 59 with open("/tmp/etetemptree.nw","w") as OUT: 60 OUT.write(nw_full) 61 62 t = Tree("/tmp/etetemptree.nw") 63 t.write(outfile='/tmp/etewritetest.nw') 64 self.assertEqual(nw_full, t.write(features=["flag","mood"])) 65 self.assertEqual(nw_topo, t.write(format=9)) 66 self.assertEqual(nw_dist, t.write(format=5)) 67 68 # Read and write newick tree from *string* (and support for NHX 69 # format) 70 t = Tree(nw_full) 71 self.assertEqual(nw_full, t.write(features=["flag","mood"])) 72 self.assertEqual(nw_topo, t.write(format=9)) 73 self.assertEqual( nw_dist, t.write(format=5)) 74 75 # Read complex newick 76 t = Tree(nw2_full) 77 self.assertEqual(nw2_full, t.write()) 78 79 # Read wierd topologies 80 t = Tree(nw_simple5) 81 self.assertEqual(nw_simple5, t.write(format=9)) 82 t = Tree(nw_simple6) 83 self.assertEqual(nw_simple6, t.write(format=9)) 84 85 #Read single node trees: 86 self.assertEqual(Tree("hola;").write(format=9), "hola;") 87 self.assertEqual(Tree("(hola);").write(format=9), "(hola);") 88 89 #Test export root features 90 t = Tree("(((A[&&NHX:name=A],B[&&NHX:name=B])[&&NHX:name=NoName],C[&&NHX:name=C])[&&NHX:name=I],(D[&&NHX:name=D],F[&&NHX:name=F])[&&NHX:name=J])[&&NHX:name=root];") 91 #print t.get_ascii() 92 self.assertEqual(t.write(format=9, features=["name"], format_root_node=True), 93 "(((A[&&NHX:name=A],B[&&NHX:name=B])[&&NHX:name=NoName],C[&&NHX:name=C])[&&NHX:name=I],(D[&&NHX:name=D],F[&&NHX:name=F])[&&NHX:name=J])[&&NHX:name=root];") 94 95 #Test exporting ordered features 96 t = Tree("((A,B),C);") 97 expected_nw = "((A:1[&&NHX:dist=1.0:name=A:support=1.0],B:1[&&NHX:0=0:1=1:2=2:3=3:4=4:5=5:6=6:7=7:8=8:9=9:a=a:b=b:c=c:d=d:dist=1.0:e=e:f=f:g=g:h=h:i=i:j=j:k=k:l=l:m=m:n=n:name=B:o=o:p=p:q=q:r=r:s=s:support=1.0:t=t:u=u:v=v:w=w])1:1[&&NHX:dist=1.0:name=:support=1.0],C:1[&&NHX:dist=1.0:name=C:support=1.0]);" 98 features = list("abcdefghijklmnopqrstuvw0123456789") 99 random.shuffle(features) 100 for letter in features: 101 (t & "B").add_feature(letter, letter) 102 self.assertEqual(expected_nw, t.write(features=[])) 103 104 # Node instance repr 105 self.assertTrue(Tree().__repr__().startswith('Tree node')) 106 107 def test_concat_trees(self): 108 t1 = Tree('((A, B), C);') 109 t2 = Tree('((a, b), c);') 110 concat_tree = t1 + t2 111 concat_tree.sort_descendants() 112 self.assertEqual(concat_tree.write(format=9), '(((A,B),C),((a,b),c));') 113 t3 = PhyloTree('((a, b), c);') 114 mixed_types = lambda: t1 + t3 115 self.assertRaises(TreeError, mixed_types) 116 117 118 def test_newick_formats(self): 119 """ tests different newick subformats """ 120 from ..parser.newick import print_supported_formats, NW_FORMAT 121 print_supported_formats() 122 123 # Let's stress a bit 124 for i in range(10): 125 t = Tree() 126 t.populate(4, random_branches=True) 127 for f in NW_FORMAT: 128 self.assertEqual(t.write(format=f), Tree(t.write(format=f),format=f).write(format=f)) 129 130 # Format 0 = ((H:1,(G:1,F:1)1:1)1:1,I:1)1:1; 131 # Format 1 = ((H:1,(G:1,F:1):1):1,I:1):1; 132 # Format 2 = ((H:1,(G:1,F:1)1:1)1:1,I:1)1:1; 133 # Format 3 = ((H:1,(G:1,F:1)NoName:1)NoName:1,I:1)NoName:1; 134 # Format 4 = ((H:1,(G:1,F:1)),I:1); 135 # Format 5 = ((H:1,(G:1,F:1):1):1,I:1):1; 136 # Format 6 = ((H,(G,F):1):1,I):1; 137 # Format 7 = ((H:1,(G:1,F:1)NoName)NoName,I:1)NoName; 138 # Format 8 = ((H,(G,F)NoName)NoName,I)NoName; 139 # Format 9 = ((H,(G,F)),I); 140 # Format 100 = ((,(,)),); 141 142 t = Tree() 143 t.populate(50, random_branches=True) 144 t.sort_descendants() 145 expected_distances = [round(x, 6) for x in [n.dist for n in t.traverse('postorder')]] 146 expected_leaf_distances = [round(x, 6) for x in [n.dist for n in t]] 147 expected_internal_distances = [round(x, 6) for x in [n.dist for n in t.traverse('postorder') if not n.is_leaf()]] 148 expected_supports = [round(x, 6) for x in [n.support for n in t.traverse('postorder') if not n.is_leaf()]] 149 expected_leaf_names = [n.name for n in t] 150 151 # Check that all formats read names correctly 152 for f in [0,1,2,3,5,6,7,8,9]: 153 t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f) 154 t2.sort_descendants() 155 observed_names = [n.name for n in t] 156 self.assertEqual(observed_names, expected_leaf_names) 157 158 # Check that all formats reading distances, recover original distances 159 for f in [0,1,2,3,5]: 160 t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f) 161 t2.sort_descendants() 162 observed_distances = [round(x, 6) for x in [n.dist for n in t2.traverse('postorder')]] 163 self.assertEqual(observed_distances, expected_distances) 164 165 # formats reading only leaf distances 166 for f in [4,7]: 167 t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f) 168 t2.sort_descendants() 169 observed_distances = [round(x, 6) for x in [n.dist for n in t2]] 170 self.assertEqual(observed_distances, expected_leaf_distances) 171 172 # formats reading only leaf distances 173 for f in [6]: 174 t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f) 175 t2.sort_descendants() 176 observed_distances = [round(x, 6) for x in [n.dist for n in t2.traverse('postorder') if not n.is_leaf()]] 177 self.assertEqual(observed_distances, expected_internal_distances) 178 179 180 # Check that all formats reading supports, recover original distances 181 #print t.get_ascii(attributes=["support"]) 182 for f in [0,2]: 183 t2 = Tree(t.write(format=f, dist_formatter="%0.6f", support_formatter="%0.6f", format_root_node=True), format=f) 184 t2.sort_descendants() 185 observed_supports = [round(x, 6) for x in [n.support for n in t2.traverse('postorder') if not n.is_leaf()]] 186 self.assertEqual(observed_supports, expected_supports) 187 188 189 # Check that formats reading supports, do not accept node names 190 for f in [0,2]: 191 # format 3 forces dumping internal node names, NoName in case is missing 192 self.assertRaises(Exception, Tree, t.write(format=3), format=f) 193 194 # Check that formats reading names, do not load supports 195 for f in [1, 3]: 196 # format 3 forces dumping internal node names, NoName in case is missing 197 t2 = Tree(t.write(format=0), format=f) 198 default_supports = set([n.support for n in t2.traverse()]) 199 self.assertEqual(set([1.0]), default_supports) 200 201 202 # Check errors reading numbers 203 error_nw1 = "((A:0.813705,(E:0.545591,D:0.411772)error:0.137245)1.000000:0.976306,C:0.074268);" 204 for f in [0, 2]: 205 self.assertRaises(NewickError, Tree, error_nw1, format=f) 206 207 error_nw2 = "((A:0.813705,(E:0.545error,D:0.411772)1.0:0.137245)1.000000:0.976306,C:0.074268);" 208 for f in [0, 1, 2]: 209 self.assertRaises(NewickError, Tree, error_nw2, format=f) 210 211 212 error_nw3 = "((A:0.813705,(E:0.545error,D:0.411772)1.0:0.137245)1.000000:0.976306,C:0.074268);" 213 for f in [0, 1, 2]: 214 self.assertRaises(NewickError, Tree, error_nw2, format=f) 215 216 # Check errors derived from reading names with weird or illegal chars 217 base_nw = "((NAME1:0.813705,(NAME2:0.545,NAME3:0.411772)NAME6:0.137245)NAME5:0.976306,NAME4:0.074268);" 218 valid_names = ['[name]', '[name', '"name"', "'name'", "'name", 'name', '[]\'"&%$!*.'] 219 error_names = ['error)', '(error', "erro()r", ":error", "error:", "err:or", ",error", "error,"] 220 for ename in error_names: 221 #print ename, base_nw.replace('NAME2', ename) 222 self.assertRaises(NewickError, Tree, base_nw.replace('NAME2', ename), format=1) 223 if not ename.startswith(','): 224 #print ename, base_nw.replace('NAME6', ename) 225 self.assertRaises(NewickError, Tree, base_nw.replace('NAME6', ename), format=1) 226 227 for vname in valid_names: 228 expected_names = set(['NAME1', vname, 'NAME3', 'NAME4']) 229 #print set([n.name for n in Tree(base_nw.replace('NAME2', vname), format=1)]) 230 self.assertEqual(set([n.name for n in Tree(base_nw.replace('NAME2', vname), format=1)]), 231 expected_names) 232 233 # invalid NHX format 234 self.assertRaises(NewickError, Tree, "(((A, B), C)[&&NHX:nameI]);") 235 # unsupported newick stream 236 self.assertRaises(NewickError, Tree, [1,2,3]) 237 238 def test_quoted_names(self): 239 complex_name = "((A:0.0001[&&NHX:hello=true],B:0.011)90:0.01[&&NHX:hello=true],(C:0.01, D:0.001)hello:0.01);" 240 # A quoted tree within a tree 241 nw1 = '(("A:0.1":1,"%s":2)"C:0.00":3,"D":4);' %complex_name 242 #escaped quotes 243 nw2 = '''(("A:\\"0.1\\"":1,"%s":2)"C:'0.00'":3,"D'sd''\'":4);''' %complex_name 244 for nw in [nw1, nw2]: 245 self.assertRaises(NewickError, Tree, newick=nw) 246 self.assertRaises(NewickError, Tree, newick=nw, quoted_node_names=True, format=0) 247 t = Tree(newick=nw, format=1, quoted_node_names=True) 248 self.assertTrue(any(n for n in t if n.name == '%s'%complex_name)) 249 # test writing and reloading tree 250 nw_back = t.write(quoted_node_names=True, format=1) 251 t2 = Tree(newick=nw, format=1, quoted_node_names=True) 252 nw_back2 = t2.write(quoted_node_names=True, format=1) 253 self.assertEqual(nw, nw_back) 254 self.assertEqual(nw, nw_back2) 255 256 def test_custom_formatting_formats(self): 257 """ test to change dist, name and support formatters """ 258 t = Tree('((A:1.111111, B:2.222222)C:3.33333, D:4.44444);', format=1) 259 t.sort_descendants() 260 261 check = [[0, '((TEST-A:1.1,TEST-B:2.2)SUP-1.0:3.3,TEST-D:4.4);'], 262 [1, '((TEST-A:1.1,TEST-B:2.2)TEST-C:3.3,TEST-D:4.4);'], 263 [2, '((TEST-A:1.1,TEST-B:2.2)SUP-1.0:3.3,TEST-D:4.4);'], 264 [3, '((TEST-A:1.1,TEST-B:2.2)TEST-C:3.3,TEST-D:4.4);'], 265 [4, '((TEST-A:1.1,TEST-B:2.2),TEST-D:4.4);'], 266 [5, '((TEST-A:1.1,TEST-B:2.2):3.3,TEST-D:4.4);'], 267 [6, '((TEST-A,TEST-B):3.3,TEST-D);'], 268 [7, '((TEST-A:1.1,TEST-B:2.2)TEST-C,TEST-D:4.4);'], 269 [8, '((TEST-A,TEST-B)TEST-C,TEST-D);'], 270 [9, '((TEST-A,TEST-B),TEST-D);']] 271 272 for f, result in check: 273 nw = t.write(format=f, dist_formatter="%0.1f", name_formatter="TEST-%s", support_formatter="SUP-%0.1f") 274 self.assertEqual(nw, result) 275 276 def test_tree_manipulation(self): 277 """ tests operations which modify tree topology """ 278 nw_tree = "((Hola:1,Turtle:1.3)1:1,(A:0.3,B:2.4)1:0.43);" 279 280 # Manipulate Topologies 281 # Adding and removing nodes (add_child, remove_child, 282 # add_sister, remove_sister). The resulting newick tree should 283 # match the nw_tree defined before. 284 t = Tree() 285 286 remove_child_except = lambda: t.remove_child(t) 287 add_sister_except = lambda: t.add_sister() 288 self.assertRaises(TreeError, remove_child_except) 289 self.assertRaises(TreeError, add_sister_except) 290 291 292 c1 = t.add_child(dist=1, support=1) 293 c2 = t.add_child(dist=0.43, support=1) 294 n = TreeNode(name="Hola", dist=1, support=1) 295 _n = c1.add_child(n) 296 c3 = _n.add_sister(name="Turtle", dist="1.3") 297 c4 = c2.add_child(name="A", dist="0.3") 298 299 c5 = c2.add_child(name="todelete") 300 _c5 = c2.remove_child(c5) 301 302 c6 = c2.add_child(name="todelete") 303 _c6 = c4.remove_sister() 304 305 c7 = c2.add_child(name="B", dist=2.4) 306 307 self.assertEqual(nw_tree, t.write()) 308 self.assertEqual(_c5, c5) 309 self.assertEqual(_c6, c6) 310 self.assertEqual(_n, n) 311 312 # Delete, 313 t = Tree("(((A, B), C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];") 314 D = t.search_nodes(name="D")[0] 315 F = t.search_nodes(name="F")[0] 316 J = t.search_nodes(name="J")[0] 317 root = t.search_nodes(name="root")[0] 318 J.delete() 319 self.assertEqual(J.up, None) 320 self.assertEqual(J in t, False) 321 self.assertEqual(D.up, root) 322 self.assertEqual(F.up, root) 323 324 # Delete preventing non dicotomic 325 t = Tree('((((A:1,B:1):1,C:1):1,D:1):1,E:1);') 326 orig_dist = t.get_distance('A') 327 C = t&('C') 328 C.delete(preserve_branch_length=True) 329 self.assertEqual(orig_dist, t.get_distance('A')) 330 331 t = Tree('((((A:1,B:1):1,C:1):1,D:1):1,E:1);') 332 orig_dist = t.get_distance('A') 333 C = t&('C') 334 C.delete(preserve_branch_length=False) 335 self.assertEqual(orig_dist, t.get_distance('A')+1) 336 337 t = Tree('((((A:1,B:1):1,C:1):1,D:1):1,E:1);') 338 orig_dist = t.get_distance('A') 339 C = t&('C') 340 C.delete(prevent_nondicotomic=False) 341 self.assertEqual(orig_dist, t.get_distance('A')) 342 343 #detach 344 t = Tree("(((A, B)[&&NHX:name=H], C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];") 345 D = t.search_nodes(name="D")[0] 346 F = t.search_nodes(name="F")[0] 347 J = t.search_nodes(name="J")[0] 348 root = t.search_nodes(name="root")[0] 349 J.detach() 350 self.assertEqual(J.up, None) 351 self.assertEqual(J in t, False) 352 self.assertEqual(set([n.name for n in t.iter_descendants()]),set(["A","B","C","I","H"])) 353 354 # sorting branches 355 t1 = Tree('((A,B),(C,D,E,F), (G,H,I));') 356 t1.ladderize() 357 self.assertEqual(t1.get_leaf_names(), [_ for _ in 'ABGHICDEF']) 358 t1.ladderize(direction=1) 359 self.assertEqual(t1.get_leaf_names(), [_ for _ in 'FEDCIHGBA']) 360 t1.sort_descendants() 361 self.assertEqual(t1.get_leaf_names(), [_ for _ in 'ABCDEFGHI']) 362 363 # prune 364 t1 = Tree("(((A, B), C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];") 365 D1 = t1.search_nodes(name="D")[0] 366 t1.prune(["A","C", D1]) 367 sys.stdout.flush() 368 self.assertEqual(set([n.name for n in t1.iter_descendants()]), set(["A","C","D","I"])) 369 370 t1 = Tree("(((A, B), C)[&&NHX:name=I], (D, F)[&&NHX:name=J])[&&NHX:name=root];") 371 D1 = t1.search_nodes(name="D")[0] 372 t1.prune(["A","B"]) 373 self.assertEqual( t1.write(), "(A:1,B:1);") 374 375 # test prune keeping internal nodes 376 377 t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1) 378 #print t1.get_ascii() 379 t1.prune(['A', 'B', 'F', 'H']) 380 #print t1.get_ascii() 381 self.assertEqual(set([n.name for n in t1.traverse()]), 382 set(['A', 'B', 'F', 'H', 'root'])) 383 384 t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1) 385 #print t1.get_ascii() 386 t1.prune(['A', 'B']) 387 #print t1.get_ascii() 388 self.assertEqual(set([n.name for n in t1.traverse()]), 389 set(['A', 'B', 'root'])) 390 391 t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1) 392 #print t1.get_ascii() 393 t1.prune(['A', 'B', 'C']) 394 #print t1.get_ascii() 395 self.assertEqual(set([n.name for n in t1.traverse()]), 396 set(['A', 'B', 'C', 'root'])) 397 398 t1 = Tree('(((((A,B)C)D,E)F,G)H,(I,J)K)root;', format=1) 399 #print t1.get_ascii() 400 t1.prune(['A', 'B', 'I']) 401 #print t1.get_ascii() 402 self.assertEqual(set([n.name for n in t1.traverse()]), 403 set(['A', 'B', 'C', 'I', 'root'])) 404 405 def test_pruninig(self): 406 # test prune preserving distances 407 for i in range(10): 408 t = Tree() 409 t.populate(40, random_branches=True) 410 orig_nw = t.write() 411 distances = {} 412 for a in t.iter_leaves(): 413 for b in t.iter_leaves(): 414 distances[(a,b)] = round(a.get_distance(b), 6) 415 416 to_keep = set(random.sample(t.get_leaves(), 6)) 417 t.prune(to_keep, preserve_branch_length=True) 418 for a,b in distances: 419 if a in to_keep and b in to_keep: 420 self.assertEqual(distances[(a,b)], round(a.get_distance(b), 6)) 421 422 # Total number of nodes is correct (no single child nodes) 423 for x in range(10): 424 t_fuzzy = Tree("(((A,B)1, C)2,(D,E)3)root;", format=1) 425 t_fuzzy.sort_descendants() 426 orig_nw = t_fuzzy.write() 427 ref_nodes = t_fuzzy.get_leaves() 428 t_fuzzy.populate(10) 429 (t_fuzzy&'1').populate(3) 430 (t_fuzzy&'2').populate(5) 431 (t_fuzzy&'3').populate(5) 432 t_fuzzy.prune(ref_nodes) 433 t_fuzzy.sort_descendants() 434 self.assertEqual(orig_nw, t_fuzzy.write()) 435 self.assertEqual(len(t_fuzzy.get_descendants()), (len(ref_nodes)*2)-2 ) 436 437 # Total number of nodes is correct (no single child nodes) 438 t = Tree() 439 sample_size = 5 440 t.populate(1000) 441 sample = random.sample(t.get_leaves(), sample_size) 442 t.prune(sample) 443 self.assertEqual(len(t), sample_size) 444 self.assertEqual(len(t.get_descendants()), (sample_size*2)-2 ) 445 446 # Test preserve branch dist when pruning 447 t = Tree() 448 t.populate(100, random_branches=True) 449 orig_leaves = t.get_leaves() 450 sample_size = 50 451 sample= random.sample(t.get_leaves(), sample_size) 452 matrix1 = ["%f" %t.get_distance(a, b) for (a,b) in itertools.product(sample, sample)] 453 t.prune(sample, preserve_branch_length=True) 454 matrix2 = ["%f" %t.get_distance(a, b) for (a,b)in itertools.product(sample, sample)] 455 456 self.assertEqual(matrix1, matrix2) 457 self.assertEqual(len(t.get_descendants()), (sample_size*2)-2 ) 458 459 def test_resolve_polytomies(self): 460 # resolve polytomy 461 t = Tree("((a,a,a,a), (b,b,b,(c,c,c)));") 462 t.resolve_polytomy() 463 t.ladderize() 464 self.assertEqual(t.write(format=9), "((a,(a,(a,a))),(b,(b,(b,(c,(c,c))))));") 465 466 t = Tree("((((a,a,a,a))), (b,b,b,(c,c,c)));") 467 t.standardize() 468 t.ladderize() 469 self.assertEqual(t.write(format=9), "((a,(a,(a,a))),(b,(b,(b,(c,(c,c))))));") 470 471 def test_common_ancestors(self): 472 # getting nodes, get_childs, get_sisters, get_tree_root, 473 # get_common_ancestor, get_nodes_by_name 474 # get_descendants_by_name, is_leaf, is_root 475 t = Tree("(((A,B)N1,C)N2[&&NHX:tag=common],D)[&&NHX:tag=root:name=root];", format=1) 476 self.assertEqual(t.get_sisters(), []) 477 478 A = t.search_nodes(name="A")[0] 479 B = t.search_nodes(name="B")[0] 480 C = t.search_nodes(name="C")[0] 481 root = (t&"root") 482 self.assertEqual("A", A.name) 483 test_not_found = lambda: t&'noffound' 484 self.assertRaises(TreeError, test_not_found) 485 486 self.assertEqual("common", A.get_common_ancestor(C).tag) 487 self.assertEqual("common", A.get_common_ancestor([C]).tag) 488 self.assertEqual("common", t.get_common_ancestor(A, C).tag) 489 self.assertEqual("common", A.get_common_ancestor(C, B).tag) 490 self.assertEqual(root, t.get_common_ancestor([A, "D"])) 491 492 self.assertEqual("root", A.get_tree_root().tag) 493 self.assertEqual("root", B.get_tree_root().tag) 494 self.assertEqual("root", C.get_tree_root().tag) 495 496 common = A.get_common_ancestor(C) 497 self.assertEqual("root", common.get_tree_root().tag) 498 499 self.assertTrue(common.get_tree_root().is_root()) 500 self.assertTrue(not A.is_root()) 501 self.assertTrue(A.is_leaf()) 502 self.assertTrue(not A.get_tree_root().is_leaf()) 503 self.assertRaises(TreeError, A.get_common_ancestor, Tree()) 504 505 # Test multiple target nodes and get_path argument 506 common, path = t.get_common_ancestor(['A', 'C'], get_path=True) 507 N1 = t & "N1" 508 N2 = t & "N2" 509 expected_path = {A: set([A, root, N1, N2]), C: set([C, N2, root])} 510 self.assertEqual(common, N2) 511 self.assertEqual(path.keys(), expected_path.keys()) 512 for k in path.keys(): 513 self.assertEqual(list(sorted(path[k], key=lambda x: x.name)), 514 list(sorted(expected_path[k], key=lambda x: x.name))) 515 516 # Test common ancestor function using self as single argument (issue #398) 517 common = A.get_common_ancestor(A) 518 self.assertEqual(common, A) 519 common = C.get_common_ancestor("C") 520 self.assertEqual(common, C) 521 common, path = C.get_common_ancestor("C", get_path=True) 522 self.assertEqual(common, C) 523 self.assertDictEqual(path, {}) 524 525 def test_getters_iters(self): 526 527 # Iter ancestors 528 t = Tree("(((((a,b)A,c)B,d)C,e)D,f)root;", format=1) 529 ancestor_names = [n.name for n in (t&"a").get_ancestors()] 530 self.assertEqual(ancestor_names, ["A", "B", "C", "D", "root"]) 531 ancestor_names = [n.name for n in (t&"B").get_ancestors()] 532 self.assertEqual(ancestor_names, ["C", "D", "root"]) 533 534 535 # Tree magic python features 536 t = Tree(nw_dflt) 537 self.assertEqual(len(t), 20) 538 self.assertTrue("Ddi0002240" in t) 539 self.assertTrue(t.children[0] in t) 540 for a in t: 541 self.assertTrue(a.name) 542 543 # Populate 544 t = Tree(nw_full) 545 prev_size= len(t) 546 t.populate(25) 547 self.assertEqual(len(t), prev_size+25) 548 for i in range(10): 549 t = Tree() 550 t.populate(100, reuse_names=False) 551 # Checks that all names are actually unique 552 self.assertEqual(len(set(t.get_leaf_names())), 100) 553 554 # Adding and removing features 555 t = Tree("(((A,B),C)[&&NHX:tag=common],D)[&&NHX:tag=root];") 556 A = t.search_nodes(name="A")[0] 557 558 # Check gettters and itters return the same 559 t = Tree(nw2_full) 560 self.assertEqual(t.get_leaf_names(), [name for name in t.iter_leaf_names()]) 561 self.assertEqual(t.get_leaves(), [name for name in t.iter_leaves()]) 562 self.assertEqual(t.get_descendants(), [n for n in t.iter_descendants()]) 563 564 self.assertEqual(set([n for n in t.traverse("preorder")]), \ 565 set([n for n in t.traverse("postorder")])) 566 self.assertTrue(t in set([n for n in t.traverse("preorder")])) 567 568 # Check order or visiting nodes 569 570 t = Tree("((3,4)2,(6,7)5)1;", format=1) 571 #t = Tree("(((A, B)C, (D, E)F)G, (H, (I, J)K)L)M;", format=1) 572 #postorder = [c for c in "ABCDEFGHIJKLM"] 573 #preorder = [c for c in reversed(postorder)] 574 #levelorder = [c for c in "MGLCFHKABDEIJ"] 575 postorder = "3426751" 576 preorder = "1234567" 577 levelorder = "1253467" 578 579 self.assertEqual(preorder, 580 ''.join([n.name for n in t.traverse("preorder")])) 581 582 self.assertEqual(postorder, 583 ''.join([n.name for n in t.traverse("postorder")])) 584 585 self.assertEqual(levelorder, 586 ''.join([n.name for n in t.traverse("levelorder")])) 587 588 # Swap childs 589 n = t.get_children() 590 t.swap_children() 591 n.reverse() 592 self.assertEqual(n, t.get_children()) 593 594 595 def test_distances(self): 596 # Distances: get_distance, get_farthest_node, 597 # get_farthest_descendant, get_midpoint_outgroup 598 t = Tree("(((A:0.1, B:0.01):0.001, C:0.0001):1.0[&&NHX:name=I], (D:0.00001):0.000001[&&NHX:name=J]):2.0[&&NHX:name=root];") 599 A = t.search_nodes(name="A")[0] 600 B = t.search_nodes(name="B")[0] 601 C = t.search_nodes(name="C")[0] 602 D = t.search_nodes(name="D")[0] 603 I = t.search_nodes(name="I")[0] 604 J = t.search_nodes(name="J")[0] 605 root = t.search_nodes(name="root")[0] 606 607 self.assertEqual(A.get_common_ancestor(I).name, "I") 608 self.assertEqual(A.get_common_ancestor(D).name, "root") 609 self.assertEqual(A.get_distance(I), 0.101) 610 self.assertEqual(A.get_distance(B), 0.11) 611 self.assertEqual(A.get_distance(A), 0) 612 self.assertEqual(I.get_distance(I), 0) 613 self.assertEqual(A.get_distance(root), root.get_distance(A)) 614 615 self.assertEqual(t.get_distance(A, root), root.get_distance(A)) 616 self.assertEqual(t.get_distance(root, A), A.get_distance(root)) 617 618 # Get_farthest_node, get_farthest_leaf 619 self.assertEqual(root.get_farthest_leaf(), (A,1.101) ) 620 self.assertEqual(root.get_farthest_node(), (A,1.101) ) 621 self.assertEqual(A.get_farthest_leaf(), (A, 0.0)) 622 self.assertEqual(A.get_farthest_node(), (D, 1.101011)) 623 self.assertEqual(I.get_farthest_node(), (D, 1.000011)) 624 625 # Topology only distances 626 t = Tree('(((A:0.5, B:1.0):1.0, C:5.0):1, (D:10.0, F:1.0):2.0):20;') 627 628 self.assertEqual(t.get_closest_leaf(), (t&'A', 2.5)) 629 self.assertEqual(t.get_farthest_leaf(), (t&'D', 12.0)) 630 self.assertEqual(t.get_farthest_leaf(topology_only=True), (t&'A', 2.0)) 631 self.assertEqual(t.get_closest_leaf(topology_only=True), (t&'C', 1.0)) 632 self.assertEqual(t.get_distance(t), 0.0) 633 self.assertEqual(t.get_distance(t, topology_only=True), 0.0) 634 self.assertEqual(t.get_distance(t&'A', topology_only=True), 2.0) 635 636 self.assertEqual((t&'F').get_farthest_node(topology_only=True), (t&'A', 3.0)) 637 self.assertEqual((t&'F').get_farthest_node(topology_only=False), (t&'D', 11.0)) 638 639 def test_rooting(self): 640 # Test set_outgroup and get_midpoint_outgroup 641 t = Tree(nw2_full) 642 YGR028W = t.get_leaves_by_name("YGR028W")[0] 643 YGR138C = t.get_leaves_by_name("YGR138C")[0] 644 d1 = YGR138C.get_distance(YGR028W) 645 nodes = t.get_descendants() 646 t.set_outgroup(t.get_midpoint_outgroup()) 647 o1, o2 = t.children[0], t.children[1] 648 nw_original = t.write() 649 d2 = YGR138C.get_distance(YGR028W) 650 self.assertEqual(d1, d2) 651 # Randomizing outgroup test: Can we recover original state 652 # after many manipulations? 653 for i in range(10): 654 for j in range(1000): 655 n = random.sample(nodes, 1)[0] 656 t.set_outgroup(n) 657 t.set_outgroup(t.get_midpoint_outgroup()) 658 self.assertEqual(set([t.children[0], t.children[1]]), set([o1, o2])) 659 ## I need to sort branches first 660 #self.assertEqual(t.write(), nw_original) 661 d3 = YGR138C.get_distance(YGR028W) 662 self.assertEqual(d1, d3) 663 664 t = Tree('(A,B,(C,D)E)root;', format=1); 665 t.sort_descendants() 666 nw_unrooted = t.write() 667 t.set_outgroup(t.get_common_ancestor('C', 'D')); 668 t.unroot() 669 t.sort_descendants() 670 self.assertEqual(nw_unrooted, t.write()) 671 672 t = Tree('(A:10,B:1,(C:1,D:1)E:1)root;', format=1); 673 t.set_outgroup(t.get_midpoint_outgroup()) 674 self.assertEqual(t.children[0].dist, 5.0) 675 self.assertEqual(t.children[1].dist, 5.0) 676 677 678 def test_unroot(self): 679 t = Tree("(('a':0.5, 'b':0.5):0.5, ('c':0.2, 'd':0.2):0.8):1;" ) 680 t2 = Tree("(('a':0.5, 'b':0.5):0.5, ('c':0.2, 'd':0.2):0.8):1;" ) 681 t.unroot(mode="keep") 682 with self.assertRaises(ValueError): 683 t.unroot(mode="new") 684 t2.unroot(mode="legacy") 685 self.assertEqual("(('c':0.2,'d':0.2)1:1.3,'a':0.5,'b':0.5);", t.write()) 686 self.assertEqual("(('c':0.2,'d':0.2)1:0.8,'a':0.5,'b':0.5);", t2.write()) 687 688 def test_tree_navigation(self): 689 t = Tree("(((A, B)H, C)I, (D, F)J)root;", format=1) 690 postorder = [n.name for n in t.traverse("postorder")] 691 preorder = [n.name for n in t.traverse("preorder")] 692 levelorder = [n.name for n in t.traverse("levelorder")] 693 694 self.assertEqual(postorder, ['A', 'B', 'H', 'C', 'I', 'D', 'F', 'J', 'root']) 695 self.assertEqual(preorder, ['root', 'I', 'H', 'A', 'B', 'C', 'J', 'D', 'F']) 696 self.assertEqual(levelorder, ['root', 'I', 'J', 'H', 'C', 'D', 'F', 'A', 'B']) 697 ancestors = [n.name for n in (t&"B").get_ancestors()] 698 self.assertEqual(ancestors, ["H", "I", "root"]) 699 self.assertEqual(t.get_ancestors(), []) 700 701 # add something of is_leaf_fn etc... 702 custom_test = lambda x: x.name in set("JCH") 703 custom_leaves = t.get_leaves(is_leaf_fn=custom_test) 704 self.assertEqual(set([n.name for n in custom_leaves]), set("JHC")) 705 706 # Test cached content 707 t = Tree() 708 t.populate(20) 709 710 cache_node = t.get_cached_content() 711 cache_node_leaves_only_false = t.get_cached_content(leaves_only=False) 712 self.assertEqual(cache_node[t], set(t.get_leaves())) 713 self.assertEqual(cache_node_leaves_only_false[t], set(t.traverse())) 714 715 cache_name = t.get_cached_content(store_attr="name") 716 cache_name_leaves_only_false = t.get_cached_content(store_attr="name", leaves_only=False) 717 self.assertEqual(cache_name[t], set(t.get_leaf_names())) 718 self.assertEqual(cache_name_leaves_only_false[t], set([n.name for n in t.traverse()])) 719 720 cache_many = t.get_cached_content(store_attr=["name", "dist", "support"]) 721 cache_many_lof = t.get_cached_content(store_attr=["name", "dist", "support"], leaves_only=False) 722 self.assertEqual(cache_many[t], set([(leaf.name, leaf.dist, leaf.support) for leaf in t.get_leaves()])) 723 self.assertEqual(cache_many_lof[t], set([(n.name, n.dist, n.support) for n in t.traverse()])) 724 725 726 #self.assertEqual(cache_name_lof[t], [t.name]) 727 728 729 def test_rooting(self): 730 """ Check branch support and distances after rooting """ 731 732 t = Tree("((((a,b)1,c)2,i)3,(e,d)4)5;", format=1) 733 t.set_outgroup(t&"a") 734 735 736 t = Tree("(((a,b)2,c)x)9;", format=1) 737 t.set_outgroup(t&"a") 738 739 # Test branch support and distances after rooting 740 SIZE = 35 741 t = Tree() 742 t.populate(SIZE, reuse_names=False) 743 t.unroot() 744 for n in t.iter_descendants(): 745 if n is not t: 746 n.support = random.random() 747 n.dist = random.random() 748 for n in t.children: 749 n.support = 0.999 750 t2 = t.copy() 751 752 names = set(t.get_leaf_names()) 753 cluster_id2support = {} 754 cluster_id2dist = {} 755 for n in t.traverse(): 756 cluster_names = set(n.get_leaf_names()) 757 cluster_names2 = names - cluster_names 758 cluster_id = '_'.join(sorted(cluster_names)) 759 cluster_id2 = '_'.join(sorted(cluster_names2)) 760 cluster_id2support[cluster_id] = n.support 761 cluster_id2support[cluster_id2] = n.support 762 763 cluster_id2dist[cluster_id] = n.dist 764 cluster_id2dist[cluster_id2] = n.dist 765 766 767 for i in range(100): 768 outgroup = random.sample(t2.get_descendants(), 1)[0] 769 t2.set_outgroup(outgroup) 770 for n in t2.traverse(): 771 cluster_names = set(n.get_leaf_names()) 772 cluster_names2 = names - cluster_names 773 cluster_id = '_'.join(sorted(cluster_names)) 774 cluster_id2 = '_'.join(sorted(cluster_names2)) 775 self.assertEqual(cluster_id2support.get(cluster_id, None), n.support) 776 self.assertEqual(cluster_id2support.get(cluster_id2, None), n.support) 777 if n.up and n.up.up: 778 self.assertEqual(cluster_id2dist.get(cluster_id, None), n.dist) 779 780 # Test unrooting 781 t = Tree() 782 t.populate(20) 783 t.unroot() 784 785 # Printing and info 786 text = t.get_ascii() 787 788 Tree().describe() 789 Tree('(a,b,c);').describe() 790 Tree('(a,(b,c));').describe() 791 792 793 def test_treeid(self): 794 t = Tree() 795 t.populate(50, random_branches=True) 796 orig_id = t.get_topology_id() 797 nodes = t.get_descendants() 798 for i in range(20): 799 for n in random.sample(nodes, 10): 800 n.swap_children() 801 self.assertEqual(t.get_topology_id(), orig_id) 802 803 804 def test_ultrametric(self): 805 806 # Convert tree to a ultrametric topology in which distance from 807 # leaf to root is always 100. Two strategies are available: 808 # balanced or fixed 809 t = Tree() 810 t.populate(100, random_branches=True) 811 t.convert_to_ultrametric(100, "balanced") 812 self.assertEqual(set([round(t.get_distance(n), 6) for n in t]), set([100.0])) 813 814 t = Tree() 815 t.populate(100, random_branches=True) 816 t.convert_to_ultrametric(100, "fixed") 817 self.assertEqual(set([round(t.get_distance(n), 6) for n in t]), set([100.0])) 818 819 t = Tree() 820 t.populate(100, random_branches=True) 821 t.convert_to_ultrametric(100, "balanced") 822 self.assertEqual(set([round(t.get_distance(n), 6) for n in t]), set([100.0])) 823 824 825 def test_expand_polytomies_rf(self): 826 gtree = Tree('((a:1, (b:1, (c:1, d:1):1):1), (e:1, (f:1, g:1):1):1);') 827 ref1 = Tree('((a:1, (b:1, c:1, d:1):1):1, (e:1, (f:1, g:1):1):1);') 828 ref2 = Tree('((a:1, (b:1, c:1, d:1):1):1, (e:1, f:1, g:1):1);') 829 for ref in [ref1, ref2]: 830 #print gtree, ref 831 gtree.robinson_foulds(ref, expand_polytomies=True)[0] 832 833 834 gtree = Tree('((g, h), (a, (b, (c, (d,( e, f))))));') 835 ref3 = Tree('((a, b, c, (d, e, f)), (g, h));') 836 ref4 = Tree('((a, b, c, d, e, f), (g, h));') 837 ref5 = Tree('((a, b, (c, d, (e, f))), (g, h));') 838 839 for ref in [ref3, ref4, ref5]: 840 #print gtree, ref 841 gtree.robinson_foulds(ref, expand_polytomies=True, polytomy_size_limit=8)[0] 842 843 844 gtree = Tree('((g, h), (a, b, (c, d, (e, f))));') 845 ref6 = Tree('((a, b, (c, d, e, f)), (g, h));') 846 ref7 = Tree('((a, (b, (c, d, e, f))), (g, h));') 847 ref8 = Tree('((a, b, c, (d, e, f)), (g, h));') 848 ref9 = Tree('((d, b, c, (a, e, f)), (g, h));') 849 850 for ref in [ref6, ref7, ref8, ref9]: 851 #print gtree, ref 852 gtree.robinson_foulds(ref, expand_polytomies=True)[0] 853 #print "REF GOOD", gtree.robinson_foulds(ref, expand_polytomies=True, polytomy_size_limit=8)[0] 854 855 gtree = Tree('((g, h), ((a, b), (c, d), (e, f)));') 856 ref10 = Tree('((g, h), ((a, c), ((b, d), (e, f))));') 857 858 for ref in [ref10]: 859 #print gtree, ref 860 gtree.robinson_foulds(ref, expand_polytomies=True, polytomy_size_limit=8)[0] 861 862 def test_tree_compare(self): 863 def _astuple(d): 864 keynames = ["norm_rf", "rf", "max_rf", "ref_edges_in_source", "source_edges_in_ref", "effective_tree_size", "source_subtrees", "treeko_dist"] 865 # print 866 # print "ref", len(d["ref_edges"]) 867 # print "src", len(d["source_edges"]) 868 # print "common", len(d["common_edges"]), d['common_edges'] 869 # print d["rf"], d["max_rf"] 870 871 return tuple([d[v] for v in keynames]) 872 873 874 ref1 = Tree('((((A, B)0.91, (C, D))0.9, (E,F)0.96), (G, H));') 875 ref2 = Tree('(((A, B)0.91, (C, D))0.9, (E,F)0.96);') 876 s1 = Tree('(((A, B)0.9, (C, D))0.9, (E,F)0.9);') 877 878 879 small = Tree("((A, B), C);") 880 # RF unrooted in too small trees for rf, but with at least one internal node 881 self.assertEqual(_astuple(small.compare(ref1, unrooted=True)), 882 ("NA", "NA", 0.0, 1.0, 1.0, 3, 1, "NA")) 883 884 small = Tree("(A, B);") 885 # RF unrooted in too small trees 886 self.assertEqual(_astuple(small.compare(ref1, unrooted=True)), 887 ("NA", "NA", 0.0, "NA", "NA", 2, 1, "NA")) 888 889 small = Tree("(A, B);") 890 # RF unrooted in too small trees 891 self.assertEqual(_astuple(small.compare(ref1, unrooted=False)), 892 ("NA", "NA", 0.0, "NA", "NA", 2, 1, "NA")) 893 894 # identical trees, 8 rooted partitions in total (4 an 4), and 6 unrooted 895 self.assertEqual(_astuple(s1.compare(ref1)), 896 (0.0, 0.0, 8, 1.0, 1.0, 6, 1, "NA")) 897 898 self.assertEqual(_astuple(s1.compare(ref1, unrooted=True)), 899 (0.0, 0.0, 6, 1.0, 1.0, 6, 1, "NA")) 900 901 # The same stats should be return discarding branches, as the topology 902 # is still identical, but branches used should be different 903 self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99, min_support_ref=.99)), 904 (0.0, 0.0, 2, 1.0, 1.0, 6, 1, "NA")) 905 906 self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99, min_support_ref=.99, unrooted=True)), 907 (0.0, 0.0, 2, 1.0, 1.0, 6, 1, "NA")) 908 909 910 self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99)), 911 (0.0, 0.0, 5, 1/4., 1.0, 6, 1, "NA")) 912 913 914 self.assertEqual(_astuple(s1.compare(ref1, min_support_source=0.99, unrooted=True)), 915 (0.0, 0.0, 4, 6/8., 1.0, 6, 1, "NA")) 916 917 918 self.assertEqual(_astuple(s1.compare(ref1, min_support_ref=0.99)), 919 (0.0, 0.0, 5, 1.0, 1/4., 6, 1, "NA")) 920 921 922 self.assertEqual(_astuple(s1.compare(ref1, min_support_ref=0.99, unrooted=True)), 923 (0.0, 0.0, 4, 1.0, 6/8., 6, 1, "NA")) 924 925 926 # Three partitions different 927 s2 = Tree('(((A, E)0.9, (C, D))0.98, (B,F)0.95);') 928 self.assertEqual(_astuple(s2.compare(ref1)), 929 (6/8., 6, 8, 1/4., 1/4., 6, 1, "NA")) 930 931 self.assertEqual(_astuple(s2.compare(ref1, unrooted=True)), 932 (4/6., 4, 6, 6/8., 6/8., 6, 1, "NA")) 933 934 # lets discard one branch from source tree. there are 4 valid edges in 935 # ref, 3 in source there is only 2 edges in common, CD and root (which 936 # should be discounted for % of found branches) 937 self.assertEqual(_astuple(s2.compare(ref1, min_support_source=0.95)), 938 (5/7., 5, 7, 1/4., 1/3., 6, 1, "NA")) 939 940 # similar in unrooted, but we don not need to discount root edges 941 self.assertEqual(_astuple(s2.compare(ref1, min_support_source=0.95, unrooted=True)), 942 (3/5., 3, 5, 6/8., 6/7., 6, 1, "NA")) 943 944 945 # totally different trees 946 s3 = Tree('(((A, C)0.9, (E, D))0.98, (B,F)0.95);') 947 self.assertEqual(_astuple(s3.compare(ref1)), 948 (1.0, 8, 8, 0.0, 0.0, 6, 1, "NA")) 949 950 951 def test_tree_diff(self): 952 # this is the result of 100 Ktreedist runs on random trees, using rooted 953 # and unrooted topologies. ETE should provide the same RF result 954 samples = [ 955 [28, True, '(((z,y),(x,(w,v))),(u,t),((s,r),((q,(p,o)),((n,(m,(l,(k,j)))),(i,(h,g))))));', '(((k,(j,(i,(h,g)))),z),(y,x),((w,v),((u,(t,(s,(r,q)))),(p,(o,(n,(m,l)))))));'], 956 [28, False, '(((t,s),((r,(q,p)),(o,n))),(((m,(l,(k,j))),(i,(h,g))),(z,(y,(x,(w,(v,u)))))));', '((((k,(j,i)),((h,g),z)),((y,(x,w)),((v,(u,t)),(s,(r,(q,p)))))),((o,n),(m,l)));'], 957 [18, True, '(((v,(u,(t,s))),((r,(q,(p,o))),((n,m),(l,k)))),(j,(i,(h,g))),(z,(y,(x,w))));', '(((z,(y,(x,w))),(v,(u,(t,s)))),((r,(q,p)),(o,(n,m))),((l,(k,(j,i))),(h,g)));'], 958 [26, True, '(((l,k),(j,i)),((h,g),(z,(y,(x,w)))),((v,(u,(t,(s,(r,q))))),((p,o),(n,m))));', '(((p,o),((n,(m,l)),(k,j))),((i,(h,g)),(z,y)),((x,(w,v)),((u,(t,s)),(r,q))));'], 959 [24, True, '(((o,(n,m)),(l,(k,(j,(i,(h,g)))))),(z,(y,x)),((w,v),((u,(t,(s,r))),(q,p))));', '(((t,(s,(r,(q,(p,o))))),(n,m)),((l,k),(j,(i,(h,g)))),((z,y),((x,w),(v,u))));'], 960 [24, True, '(((y,(x,(w,v))),(u,t)),((s,(r,(q,(p,o)))),(n,m)),((l,k),((j,(i,(h,g))),z)));', '(((z,(y,(x,w))),(v,(u,t))),(s,(r,(q,(p,(o,(n,(m,(l,k)))))))),(j,(i,(h,g))));'], 961 [28, False, '(((p,(o,(n,(m,l)))),((k,(j,i)),(h,g))),((z,y),((x,(w,(v,u))),(t,(s,(r,q))))));', '((((t,(s,r)),(q,p)),((o,n),(m,(l,(k,(j,i)))))),(((h,g),(z,(y,(x,w)))),(v,u)));'], 962 [28, True, '((((i,(h,g)),z),(y,x)),((w,v),((u,(t,(s,r))),(q,p))),((o,n),(m,(l,(k,j)))));', '((((h,g),z),(y,x)),(w,(v,u)),((t,s),((r,(q,p)),((o,(n,m)),(l,(k,(j,i)))))));'], 963 [28, True, '(((x,(w,(v,(u,(t,(s,(r,(q,(p,o))))))))),((n,(m,l)),(k,(j,i)))),(h,g),(z,y));', '(((u,t),(s,r)),((q,p),(o,(n,m))),(((l,(k,(j,i))),((h,g),(z,(y,x)))),(w,v)));'], 964 [22, False, '(((x,(w,(v,u))),((t,(s,r)),(q,p))),((o,(n,(m,l))),((k,j),((i,(h,g)),(z,y)))));', '(((z,(y,(x,(w,(v,u))))),(t,(s,r))),((q,(p,(o,(n,m)))),((l,k),(j,(i,(h,g))))));'], 965 [26, True, '((z,(y,(x,w))),(v,(u,(t,s))),((r,(q,(p,(o,(n,m))))),((l,k),(j,(i,(h,g))))));', '(((v,(u,t)),((s,r),((q,(p,o)),(n,(m,l))))),((k,j),((i,(h,g)),z)),(y,(x,w)));'], 966 [34, False, '((((i,(h,g)),(z,(y,x))),(w,v)),((u,t),((s,r),((q,(p,(o,n))),(m,(l,(k,j)))))));', '(((p,(o,(n,(m,(l,k))))),((j,i),(h,g))),(z,(y,(x,(w,(v,(u,(t,(s,(r,q))))))))));'], 967 [30, False, '(((i,(h,g)),(z,y)),((x,w),((v,(u,(t,(s,(r,q))))),(p,(o,(n,(m,(l,(k,j)))))))));', '((((l,k),(j,(i,(h,g)))),(z,(y,(x,w)))),((v,u),((t,s),((r,(q,p)),(o,(n,m))))));'], 968 [26, False, '(((v,(u,t)),((s,(r,q)),((p,o),((n,m),((l,k),(j,i)))))),((h,g),(z,(y,(x,w)))));', '(((y,(x,(w,v))),(u,(t,s))),(((r,q),((p,o),(n,(m,(l,k))))),((j,i),((h,g),z))));'], 969 [20, False, '(((u,(t,s)),(r,q)),(((p,o),((n,m),((l,k),((j,i),((h,g),z))))),(y,(x,(w,v)))));', '((((u,t),(s,r)),(((q,p),(o,(n,m))),(((l,k),(j,i)),((h,g),z)))),((y,x),(w,v)));'], 970 [20, True, '(((y,x),(w,v)),((u,(t,s)),((r,q),(p,(o,(n,(m,(l,k))))))),((j,(i,(h,g))),z));', '(((r,q),((p,o),(n,(m,(l,(k,j)))))),((i,(h,g)),(z,(y,(x,(w,v))))),(u,(t,s)));'], 971 [24, True, '((((k,(j,i)),(h,g)),((z,(y,(x,w))),((v,(u,t)),(s,r)))),(q,(p,(o,n))),(m,l));', '((((s,r),((q,p),(o,(n,m)))),((l,k),((j,i),((h,g),z)))),(y,x),(w,(v,(u,t))));'], 972 [18, True, '((w,(v,(u,(t,s)))),(r,q),((p,(o,n)),((m,(l,k)),((j,(i,(h,g))),(z,(y,x))))));', '(((y,x),((w,v),(u,(t,s)))),((r,(q,(p,(o,n)))),(m,l)),((k,j),((i,(h,g)),z)));'], 973 [26, True, '(((j,(i,(h,g))),(z,(y,(x,(w,(v,(u,t))))))),(s,r),((q,p),((o,(n,m)),(l,k))));', '(((s,(r,(q,(p,(o,(n,(m,l))))))),(k,j)),((i,(h,g)),(z,y)),((x,(w,v)),(u,t)));'], 974 [30, True, '((((r,(q,(p,(o,n)))),((m,l),(k,(j,i)))),((h,g),z)),(y,(x,(w,v))),(u,(t,s)));', '(((u,t),(s,r)),((q,p),(o,(n,(m,(l,(k,j)))))),(((i,(h,g)),(z,(y,x))),(w,v)));'], 975 [30, False, '((((m,(l,k)),(j,i)),(((h,g),(z,y)),(x,w))),((v,u),(t,(s,(r,(q,(p,(o,n))))))));', '(((u,t),((s,(r,q)),(p,(o,(n,(m,(l,k))))))),((j,(i,(h,g))),(z,(y,(x,(w,v))))));'], 976 [22, False, '(((k,(j,i)),(h,g)),((z,(y,x)),((w,(v,(u,(t,(s,r))))),((q,(p,(o,n))),(m,l)))));', '(((w,(v,u)),((t,(s,r)),((q,p),((o,(n,(m,l))),((k,(j,i)),((h,g),z)))))),(y,x));'], 977 [26, False, '(((x,(w,(v,(u,(t,s))))),(r,q)),((p,(o,(n,(m,l)))),((k,j),((i,(h,g)),(z,y)))));', '(((o,(n,m)),(l,(k,j))),(((i,(h,g)),(z,y)),((x,w),((v,u),((t,(s,r)),(q,p))))));'], 978 [28, True, '(((x,(w,v)),(u,(t,s))),((r,(q,(p,(o,(n,m))))),(l,(k,(j,(i,(h,g)))))),(z,y));', '((((i,(h,g)),(z,(y,x))),((w,v),((u,t),(s,(r,(q,p)))))),(o,n),((m,l),(k,j)));'], 979 [20, False, '((((m,l),(k,(j,(i,(h,g))))),(z,y)),((x,(w,(v,(u,(t,s))))),(r,(q,(p,(o,n))))));', '((((m,l),((k,(j,i)),(h,g))),(z,(y,(x,(w,v))))),((u,t),(s,(r,(q,(p,(o,n)))))));'], 980 [26, True, '(((o,(n,(m,(l,k)))),(j,i)),((h,g),(z,y)),((x,(w,(v,(u,(t,s))))),(r,(q,p))));', '((((t,(s,(r,(q,(p,(o,n)))))),(m,(l,k))),((j,i),(h,g))),(z,(y,x)),(w,(v,u)));'], 981 [22, False, '((((p,o),((n,m),((l,k),(j,i)))),((h,g),(z,y))),((x,(w,(v,u))),((t,s),(r,q))));', '((((v,(u,(t,s))),(r,q)),((p,o),((n,m),(l,k)))),(((j,i),(h,g)),(z,(y,(x,w)))));'], 982 [28, False, '((((r,(q,(p,(o,n)))),(m,(l,k))),(((j,i),(h,g)),((z,y),(x,w)))),((v,u),(t,s)));', '((((k,j),((i,(h,g)),(z,y))),(x,w)),(((v,(u,t)),(s,r)),((q,p),((o,n),(m,l)))));'], 983 [20, True, '((((q,(p,o)),(n,m)),((l,k),((j,i),(h,g)))),(z,(y,x)),((w,v),(u,(t,(s,r)))));', '((((l,(k,(j,i))),(h,g)),((z,y),(x,(w,v)))),(u,t),((s,(r,(q,(p,o)))),(n,m)));'], 984 [28, False, '(((t,(s,r)),(q,(p,o))),(((n,(m,(l,k))),(j,(i,(h,g)))),((z,y),(x,(w,(v,u))))));', '(((w,(v,u)),(t,s)),(((r,(q,p)),(o,n)),(((m,l),((k,j),((i,(h,g)),z))),(y,x))));'], 985 [24, True, '((((h,g),(z,y)),((x,(w,(v,u))),(t,(s,(r,q))))),(p,o),((n,m),((l,k),(j,i))));', '(((t,s),((r,(q,p)),((o,(n,(m,l))),((k,j),(i,(h,g)))))),(z,y),(x,(w,(v,u))));'], 986 [20, True, '(((p,o),(n,(m,(l,(k,(j,i)))))),((h,g),z),((y,(x,w)),((v,u),(t,(s,(r,q))))));', '(((y,(x,w)),(v,(u,t))),((s,r),(q,p)),((o,(n,m)),((l,(k,(j,i))),((h,g),z))));'], 987 [32, True, '((((s,(r,q)),((p,(o,n)),(m,(l,k)))),((j,(i,(h,g))),(z,y))),(x,w),(v,(u,t)));', '(((u,(t,(s,r))),((q,(p,o)),((n,(m,l)),(k,(j,i))))),((h,g),(z,(y,x))),(w,v));'], 988 [26, True, '(((z,(y,x)),(w,(v,(u,t)))),(s,(r,(q,(p,(o,n))))),((m,l),(k,(j,(i,(h,g))))));', '(((u,t),((s,r),((q,p),((o,n),((m,(l,k)),((j,i),((h,g),z))))))),(y,x),(w,v));'], 989 [10, True, '(((p,o),((n,m),((l,(k,(j,i))),((h,g),(z,y))))),(x,(w,(v,u))),((t,s),(r,q)));', '((((n,m),((l,(k,(j,i))),((h,g),(z,y)))),(x,w)),(v,(u,(t,(s,(r,q))))),(p,o));'], 990 [30, True, '((((h,g),z),((y,x),((w,v),(u,t)))),(s,r),((q,p),((o,n),((m,l),(k,(j,i))))));', '((((v,(u,(t,(s,r)))),(q,(p,o))),((n,m),((l,k),(j,(i,(h,g)))))),(z,y),(x,w));'], 991 [30, False, '(((q,(p,o)),((n,m),((l,(k,(j,(i,(h,g))))),(z,y)))),((x,(w,v)),(u,(t,(s,r)))));', '((((t,s),((r,q),((p,o),(n,m)))),((l,k),(j,i))),(((h,g),z),((y,(x,w)),(v,u))));'], 992 [24, False, '(((p,o),(n,m)),(((l,(k,(j,i))),(h,g)),((z,y),((x,w),((v,u),(t,(s,(r,q))))))));', '((x,(w,v)),((u,(t,(s,(r,q)))),((p,(o,(n,(m,(l,(k,(j,(i,(h,g))))))))),(z,y))));'], 993 [28, False, '(((z,y),((x,w),((v,u),(t,s)))),((r,(q,(p,(o,(n,m))))),((l,k),((j,i),(h,g)))));', '((((s,(r,q)),((p,o),((n,(m,l)),(k,(j,(i,(h,g))))))),(z,y)),((x,w),(v,(u,t))));'], 994 [24, False, '((((o,n),((m,l),((k,(j,i)),(h,g)))),(z,(y,x))),((w,(v,(u,(t,(s,r))))),(q,p)));', '(((q,(p,(o,(n,m)))),((l,(k,j)),(i,(h,g)))),(z,(y,(x,(w,(v,(u,(t,(s,r)))))))));'], 995 [22, True, '(((p,(o,(n,m))),((l,k),((j,i),((h,g),(z,y))))),(x,w),((v,u),((t,s),(r,q))));', '(((u,(t,(s,(r,(q,(p,(o,(n,m)))))))),((l,k),((j,i),((h,g),(z,(y,x)))))),w,v);'], 996 [28, False, '((((r,q),((p,o),(n,(m,l)))),((k,(j,i)),(h,g))),((z,y),((x,(w,v)),(u,(t,s)))));', '(((h,g),z),((y,x),((w,v),((u,t),((s,(r,(q,(p,(o,(n,m)))))),(l,(k,(j,i))))))));'], 997 [30, True, '((((h,g),z),((y,(x,(w,(v,u)))),((t,s),((r,(q,(p,o))),(n,m))))),(l,k),(j,i));', '((((o,n),((m,(l,(k,j))),((i,(h,g)),z))),(y,(x,(w,v)))),(u,(t,s)),(r,(q,p)));'], 998 [30, True, '(((v,u),(t,(s,(r,(q,p))))),((o,(n,m)),((l,(k,j)),((i,(h,g)),z))),(y,(x,w)));', '((((m,(l,k)),((j,i),(h,g))),(z,y)),(x,w),((v,(u,(t,(s,(r,q))))),(p,(o,n))));'], 999 [26, True, '(((q,p),((o,(n,(m,l))),(k,(j,i)))),((h,g),z),((y,x),((w,(v,(u,t))),(s,r))));', '((((j,(i,(h,g))),(z,(y,x))),((w,v),(u,t))),(s,(r,q)),((p,o),(n,(m,(l,k)))));'], 1000 [20, False, '((((o,(n,m)),((l,k),((j,i),((h,g),z)))),(y,x)),(((w,v),(u,t)),((s,r),(q,p))));', '((((j,i),((h,g),z)),((y,x),(w,(v,(u,(t,(s,r))))))),((q,p),((o,n),(m,(l,k)))));'], 1001 [30, False, '(((x,w),(v,(u,(t,(s,(r,(q,(p,(o,(n,m)))))))))),((l,k),((j,(i,(h,g))),(z,y))));', '(((m,l),((k,(j,(i,(h,g)))),z)),((y,(x,(w,(v,(u,t))))),((s,r),((q,p),(o,n)))));'], 1002 [32, True, '((((y,x),(w,v)),((u,(t,(s,r))),(q,(p,o)))),((n,m),(l,(k,j))),((i,(h,g)),z));', '(((m,l),(k,(j,i))),((h,g),z),((y,(x,w)),((v,u),((t,s),(r,(q,(p,(o,n))))))));'], 1003 [28, True, '(((v,u),((t,(s,(r,(q,p)))),((o,n),((m,l),(k,(j,(i,(h,g)))))))),(z,y),(x,w));', '((((n,m),((l,k),((j,i),((h,g),(z,(y,(x,(w,(v,u))))))))),(t,s)),(r,q),(p,o));'], 1004 [32, False, '(((r,(q,p)),(o,n)),(((m,(l,k)),(j,i)),(((h,g),(z,y)),((x,w),((v,u),(t,s))))));', '(((y,x),((w,v),(u,(t,(s,r))))),(((q,(p,(o,n))),(m,l)),((k,(j,(i,(h,g)))),z)));'], 1005 [20, True, '(((w,v),((u,(t,(s,r))),((q,p),((o,(n,(m,l))),((k,j),((i,(h,g)),z)))))),y,x);', '(((w,v),((u,t),(s,(r,q)))),((p,o),((n,(m,l)),(k,j))),((i,(h,g)),(z,(y,x))));'], 1006 [24, False, '(((x,(w,v)),((u,(t,s)),(r,q))),(((p,o),((n,(m,l)),(k,j))),((i,(h,g)),(z,y))));', '((((i,(h,g)),z),((y,x),(w,v))),((u,(t,s)),((r,(q,(p,(o,(n,m))))),(l,(k,j)))));'], 1007 [22, False, '((((k,(j,(i,(h,g)))),(z,(y,x))),((w,v),(u,t))),((s,(r,(q,(p,o)))),(n,(m,l))));', '(((w,v),(u,(t,(s,(r,(q,(p,o))))))),(((n,m),((l,(k,(j,i))),((h,g),z))),(y,x)));'], 1008 [28, True, '(((x,w),((v,u),((t,s),(r,(q,p))))),((o,n),(m,l)),((k,(j,i)),((h,g),(z,y))));', '((((p,o),(n,m)),((l,(k,(j,i))),((h,g),z))),(y,(x,(w,v))),((u,t),(s,(r,q))));'], 1009 [30, False, '(((q,p),((o,(n,(m,l))),((k,(j,(i,(h,g)))),z))),((y,x),((w,(v,u)),(t,(s,r)))));', '((((m,(l,k)),((j,(i,(h,g))),z)),(y,(x,w))),((v,(u,(t,(s,(r,q))))),(p,(o,n))));'], 1010 [30, False, '(((y,x),((w,(v,(u,(t,(s,r))))),(q,p))),((o,(n,(m,(l,(k,(j,i)))))),((h,g),z)));', '((((t,(s,(r,q))),((p,(o,(n,(m,l)))),((k,(j,i)),(h,g)))),(z,y)),((x,w),(v,u)));'], 1011 [20, False, '(((u,(t,s)),(r,(q,(p,(o,(n,(m,(l,(k,j))))))))),(((i,(h,g)),z),(y,(x,(w,v)))));', '(((o,n),(m,(l,(k,j)))),(((i,(h,g)),(z,y)),((x,(w,v)),((u,(t,(s,r))),(q,p)))));'], 1012 [26, False, '(((t,s),((r,(q,(p,(o,n)))),(m,(l,k)))),(((j,i),((h,g),z)),((y,(x,w)),(v,u))));', '(((r,(q,(p,o))),((n,(m,(l,k))),((j,i),(h,g)))),((z,(y,(x,(w,v)))),(u,(t,s))));'], 1013 [28, True, '((((r,q),((p,(o,(n,(m,l)))),((k,(j,i)),(h,g)))),(z,(y,(x,w)))),(v,u),(t,s));', '(((x,(w,(v,(u,(t,s))))),(r,(q,(p,o)))),(n,m),((l,k),((j,(i,(h,g))),(z,y))));'], 1014 [28, False, '(((t,s),((r,(q,p)),((o,n),(m,(l,(k,(j,i))))))),(((h,g),(z,y)),(x,(w,(v,u)))));', '((((h,g),(z,(y,(x,(w,v))))),(u,(t,(s,r)))),((q,(p,(o,(n,m)))),(l,(k,(j,i)))));'], 1015 [26, True, '((((q,(p,o)),((n,m),((l,(k,(j,i))),(h,g)))),(z,(y,x))),(w,v),(u,(t,(s,r))));', '(((y,x),(w,(v,u))),((t,(s,r)),((q,p),(o,n))),((m,(l,k)),((j,(i,(h,g))),z)));'], 1016 [28, False, '((((q,(p,(o,n))),((m,(l,k)),((j,(i,(h,g))),z))),(y,x)),((w,(v,(u,t))),(s,r)));', '(((z,(y,x)),(w,v)),(((u,t),((s,(r,(q,p))),((o,n),(m,l)))),((k,(j,i)),(h,g))));'], 1017 [22, True, '(((x,w),((v,(u,(t,s))),(r,q))),((p,(o,n)),((m,(l,k)),(j,(i,(h,g))))),(z,y));', '((((j,(i,(h,g))),(z,(y,x))),(w,(v,u))),((t,s),((r,q),(p,o))),((n,m),(l,k)));'], 1018 [26, False, '((((n,(m,l)),(k,j)),(((i,(h,g)),(z,y)),((x,w),((v,u),(t,s))))),((r,q),(p,o)));', '(((v,u),(t,s)),(((r,(q,(p,(o,n)))),((m,(l,k)),(j,i))),((h,g),(z,(y,(x,w))))));'], 1019 [32, False, '((((n,(m,(l,(k,j)))),((i,(h,g)),z)),(y,x)),((w,v),((u,(t,(s,r))),(q,(p,o)))));', '((((v,u),(t,(s,(r,(q,p))))),((o,(n,(m,(l,k)))),(j,(i,(h,g))))),((z,y),(x,w)));'], 1020 [20, False, '((((q,(p,(o,n))),(m,l)),((k,(j,(i,(h,g)))),z)),((y,(x,(w,(v,(u,t))))),(s,r)));', '(((w,(v,(u,t))),(s,r)),(((q,p),(o,n)),(((m,l),(k,(j,i))),((h,g),(z,(y,x))))));'], 1021 [20, True, '(((z,(y,(x,w))),(v,u)),((t,(s,r)),(q,(p,o))),((n,(m,l)),((k,(j,i)),(h,g))));', '((((q,(p,(o,n))),(m,l)),((k,j),(i,(h,g)))),(z,y),((x,w),((v,u),(t,(s,r)))));'], 1022 [34, False, '(((w,(v,(u,(t,(s,(r,q)))))),(p,o)),(((n,m),(l,(k,j))),((i,(h,g)),(z,(y,x)))));', '(((y,(x,(w,(v,u)))),(t,(s,r))),(((q,(p,(o,(n,(m,(l,k)))))),(j,i)),((h,g),z)));'], 1023 [26, False, '(((y,x),(w,(v,(u,t)))),(((s,r),((q,(p,o)),(n,(m,l)))),((k,(j,(i,(h,g)))),z)));', '(((s,(r,(q,(p,o)))),(n,m)),(((l,k),((j,i),((h,g),(z,(y,(x,w)))))),(v,(u,t))));'], 1024 [30, False, '(((v,(u,t)),((s,r),((q,p),((o,(n,(m,(l,k)))),(j,i))))),(((h,g),z),(y,(x,w))));', '(((y,(x,(w,v))),((u,(t,s)),(r,(q,(p,o))))),((n,(m,l)),((k,(j,i)),((h,g),z))));'], 1025 [26, False, '(((y,x),(w,v)),(((u,t),((s,(r,(q,p))),(o,n))),((m,(l,k)),((j,i),((h,g),z)))));', '((((s,(r,q)),((p,(o,n)),((m,l),(k,(j,i))))),((h,g),z)),((y,(x,w)),(v,(u,t))));'], 1026 [22, True, '(((w,v),(u,t)),((s,r),((q,p),((o,(n,m)),((l,k),((j,i),(h,g)))))),(z,(y,x)));', '(((z,y),(x,(w,(v,u)))),(t,(s,r)),((q,(p,o)),((n,m),((l,(k,(j,i))),(h,g)))));'], 1027 [28, False, '(((y,x),(w,(v,(u,t)))),(((s,(r,q)),((p,o),(n,(m,(l,k))))),((j,i),((h,g),z))));', '((((i,(h,g)),(z,(y,x))),((w,(v,u)),(t,s))),((r,q),((p,o),((n,m),(l,(k,j))))));'], 1028 [26, False, '(((v,(u,(t,s))),(r,(q,p))),(((o,n),((m,(l,(k,j))),((i,(h,g)),(z,y)))),(x,w)));', '(((q,p),((o,n),((m,l),((k,j),((i,(h,g)),z))))),(y,(x,(w,(v,(u,(t,(s,r))))))));'], 1029 [26, True, '(((t,(s,(r,q))),((p,o),((n,(m,l)),((k,j),((i,(h,g)),z))))),(y,x),(w,(v,u)));', '(((z,y),(x,w)),(v,u),((t,(s,r)),((q,(p,(o,(n,(m,l))))),((k,(j,i)),(h,g)))));'], 1030 [30, True, '(((w,(v,(u,(t,(s,r))))),(q,p)),((o,(n,m)),((l,k),(j,i))),(((h,g),z),(y,x)));', '((((p,o),(n,(m,(l,(k,(j,(i,(h,g)))))))),(z,(y,x))),(w,(v,u)),((t,s),(r,q)));'], 1031 [26, True, '((((i,(h,g)),(z,y)),(x,w)),((v,u),((t,(s,r)),(q,p))),((o,n),(m,(l,(k,j)))));', '(((l,k),((j,i),((h,g),(z,y)))),(x,w),((v,u),((t,s),((r,(q,(p,o))),(n,m)))));'], 1032 [26, False, '(((x,w),((v,(u,(t,s))),((r,(q,p)),((o,(n,(m,(l,k)))),((j,i),(h,g)))))),(z,y));', '(((p,(o,(n,m))),(l,k)),(((j,i),(h,g)),((z,y),((x,(w,v)),((u,t),(s,(r,q)))))));'], 1033 [24, True, '(((x,w),((v,(u,t)),(s,r))),((q,p),(o,(n,(m,(l,k))))),((j,i),((h,g),(z,y))));', '(((h,g),(z,y)),(x,(w,(v,u))),((t,(s,r)),(q,(p,(o,(n,(m,(l,(k,(j,i))))))))));'], 1034 [24, True, '(((y,x),(w,v)),((u,t),((s,r),((q,p),((o,n),(m,(l,k)))))),((j,(i,(h,g))),z));', '((((r,(q,p)),(o,(n,(m,(l,(k,(j,(i,(h,g))))))))),(z,y)),(x,(w,v)),(u,(t,s)));'], 1035 [28, False, '(((y,(x,(w,v))),((u,t),((s,(r,q)),((p,(o,n)),((m,l),(k,(j,i))))))),((h,g),z));', '(((v,u),(t,(s,(r,(q,(p,(o,n))))))),(((m,l),((k,j),((i,(h,g)),z))),(y,(x,w))));'], 1036 [26, True, '((((h,g),z),((y,x),((w,(v,u)),((t,(s,(r,q))),(p,(o,n)))))),(m,(l,k)),(j,i));', '((z,y),(x,(w,(v,(u,t)))),((s,r),((q,p),((o,n),((m,(l,k)),(j,(i,(h,g))))))));'], 1037 [24, True, '(((u,t),(s,r)),((q,p),((o,n),((m,(l,(k,(j,(i,(h,g)))))),z))),(y,(x,(w,v))));', '((((j,(i,(h,g))),z),(y,x)),(w,(v,(u,t))),((s,(r,(q,p))),((o,(n,m)),(l,k))));'], 1038 [30, True, '(((t,(s,r)),((q,p),((o,n),(m,(l,(k,j)))))),((i,(h,g)),z),((y,x),(w,(v,u))));', '((((w,(v,(u,t))),(s,(r,q))),((p,(o,(n,m))),(l,k))),((j,i),(h,g)),(z,(y,x)));'], 1039 [30, False, '((((x,(w,v)),(u,t)),((s,(r,q)),(p,o))),(((n,m),((l,k),((j,i),(h,g)))),(z,y)));', '((r,q),((p,(o,n)),((m,(l,(k,(j,i)))),((h,g),(z,(y,(x,(w,(v,(u,(t,s)))))))))));'], 1040 [28, True, '((((k,j),((i,(h,g)),(z,(y,x)))),(w,v)),(u,t),((s,(r,q)),(p,(o,(n,(m,l))))));', '(((z,y),(x,w)),(v,(u,(t,(s,(r,q))))),((p,o),((n,(m,(l,(k,(j,i))))),(h,g))));'], 1041 [18, True, '(((t,s),((r,(q,(p,o))),(n,m))),((l,(k,j)),((i,(h,g)),(z,y))),((x,w),(v,u)));', '((((l,k),(j,i)),(((h,g),(z,y)),(x,w))),((v,u),(t,s)),((r,q),((p,o),(n,m))));'], 1042 [26, True, '(((h,g),z),(y,(x,w)),((v,(u,(t,s))),((r,(q,p)),((o,(n,(m,l))),(k,(j,i))))));', '(((s,r),(q,p)),((o,n),(m,l)),(((k,j),((i,(h,g)),(z,(y,x)))),(w,(v,(u,t)))));'], 1043 [30, True, '(((x,w),((v,(u,(t,(s,(r,(q,(p,(o,n)))))))),((m,(l,k)),((j,i),(h,g))))),z,y);', '((((h,g),z),(y,x)),((w,v),((u,(t,s)),(r,q))),((p,(o,(n,(m,l)))),(k,(j,i))));'], 1044 [30, False, '(((v,(u,(t,(s,(r,q))))),((p,(o,(n,m))),((l,(k,(j,i))),(h,g)))),((z,y),(x,w)));', '(((v,u),((t,(s,(r,(q,(p,o))))),(n,(m,(l,(k,j)))))),((i,(h,g)),(z,(y,(x,w)))));'], 1045 [22, True, '(((z,y),((x,(w,v)),((u,(t,(s,r))),(q,(p,o))))),(n,m),((l,k),(j,(i,(h,g)))));', '(((r,q),(p,(o,(n,m)))),((l,(k,(j,(i,(h,g))))),(z,y)),((x,w),(v,(u,(t,s)))));'], 1046 [30, True, '(((x,w),((v,(u,(t,(s,r)))),(q,p))),((o,n),(m,l)),((k,j),((i,(h,g)),(z,y))));', '((((p,o),((n,(m,(l,k))),((j,i),(h,g)))),((z,y),(x,(w,v)))),(u,t),(s,(r,q)));'], 1047 [32, False, '(((r,(q,p)),(o,(n,m))),(((l,(k,(j,i))),(h,g)),((z,(y,(x,(w,(v,u))))),(t,s))));', '((((j,(i,(h,g))),(z,y)),(x,(w,(v,(u,t))))),(((s,r),(q,(p,o))),((n,m),(l,k))));'], 1048 [30, False, '((((q,p),((o,(n,(m,(l,k)))),((j,(i,(h,g))),(z,y)))),(x,w)),((v,u),(t,(s,r))));', '((((o,(n,m)),((l,(k,(j,i))),((h,g),z))),(y,x)),((w,v),((u,t),((s,r),(q,p)))));'], 1049 [28, False, '((((s,r),((q,(p,o)),(n,(m,l)))),((k,(j,i)),(h,g))),((z,(y,x)),(w,(v,(u,t)))));', '(((m,l),(k,j)),(((i,(h,g)),z),((y,x),((w,(v,(u,(t,(s,r))))),((q,p),(o,n))))));'], 1050 [20, True, '((((z,y),(x,(w,(v,u)))),((t,s),(r,q))),((p,o),(n,(m,l))),((k,(j,i)),(h,g)));', '(((j,i),(h,g)),(z,(y,x)),((w,(v,u)),((t,(s,(r,q))),((p,o),((n,m),(l,k))))));'], 1051 [20, False, '(((v,u),((t,s),(r,q))),(((p,o),(n,(m,l))),(((k,(j,i)),((h,g),z)),(y,(x,w)))));', '((((s,(r,q)),(p,o)),(((n,(m,l)),(k,(j,i))),((h,g),z))),((y,x),((w,v),(u,t))));'], 1052 [28, True, '((z,y),(x,w),((v,u),((t,(s,(r,q))),((p,(o,(n,m))),(l,(k,(j,(i,(h,g)))))))));', '((((r,q),((p,o),((n,m),((l,k),(j,i))))),((h,g),(z,(y,x)))),(w,v),(u,(t,s)));'], 1053 [24, False, '((((k,(j,(i,(h,g)))),(z,y)),(x,(w,v))),(((u,t),(s,(r,q))),((p,o),(n,(m,l)))));', '(((w,v),(u,(t,s))),(((r,(q,(p,o))),((n,m),(l,(k,(j,(i,(h,g))))))),(z,(y,x))));'], 1054 [24, True, '((((n,m),((l,(k,j)),(i,(h,g)))),(z,y)),(x,(w,v)),((u,(t,(s,(r,q)))),(p,o)));', '(((r,q),(p,o)),((n,(m,l)),((k,j),((i,(h,g)),z))),((y,x),(w,(v,(u,(t,s))))));']] 1055 1056 # test RF exceptions 1057 t1 = Tree('(a,b,(c,d,e));') 1058 t2 = Tree('((a,b),(c,d,e));') 1059 # testing unrooted trees 1060 self.assertRaises(TreeError, t1.robinson_foulds, t2=t2) 1061 1062 # expand polytomies and unrooted trees 1063 self.assertRaises(TreeError, t1.robinson_foulds, t2=t2, 1064 unrooted_trees=True, expand_polytomies=True) 1065 1066 # usisng expand_polytomies and correct_by_size at the same time 1067 self.assertRaises(TreeError, t1.robinson_foulds, t2=t1, 1068 unrooted_trees=True, expand_polytomies=True, 1069 correct_by_polytomy_size=True) 1070 1071 # correct by size when polytomies in both sides 1072 self.assertRaises(TreeError, t1.robinson_foulds, t2=t1, 1073 unrooted_trees=True, correct_by_polytomy_size=True) 1074 1075 # polytomy larger than deafult limit 1076 self.assertRaises(TreeError, t2.robinson_foulds, t2=Tree('(a, (b,c,d,e,f,g,h));'), 1077 expand_polytomies=True) 1078 1079 # duplicated items 1080 t3 = Tree('(a, (b, (c, c)));') 1081 self.assertRaises(TreeError, t3.robinson_foulds, t2=t2) 1082 self.assertRaises(TreeError, t2.robinson_foulds, t2=t3) 1083 1084 1085 1086 # test RF using a knonw set of results 1087 for RF, unrooted, nw1, nw2 in samples: 1088 t1 = Tree(nw1) 1089 t2 = Tree(nw2) 1090 rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted) 1091 real_max = (20*2) - 4 if not unrooted else (20*2) - 6 1092 1093 self.assertEqual(len(names), 20) 1094 self.assertEqual(rf_max, real_max) 1095 self.assertEqual(rf, RF) 1096 1097 comp = t1.compare(t2, unrooted=unrooted) 1098 self.assertEqual(20, comp['effective_tree_size']) 1099 self.assertEqual(rf_max, comp['max_rf']) 1100 self.assertEqual(RF, comp['rf']) 1101 # Let's insert some random nodes, that should be ignored 1102 for target in random.sample([n for n in t2.get_descendants() if not n.is_leaf()], 5): 1103 target.populate(5) 1104 comp = t1.compare(t2, unrooted=unrooted) 1105 self.assertEqual(20, comp['effective_tree_size']) 1106 self.assertEqual(rf_max, comp['max_rf']) 1107 self.assertEqual(RF, comp['rf']) 1108 1109 # test treeko functionality 1110 t = PhyloTree('((((A,B),C), ((A,B),C)), (((A,B),C), ((A,B),C)));') 1111 ref = Tree('((A,B),C);') 1112 comp = t.compare(ref, has_duplications=True) 1113 #from pprint import pprint 1114 #pprint(comp) 1115 self.assertEqual(comp['effective_tree_size'], 3) 1116 self.assertEqual(comp['treeko_dist'], 0.0) 1117 self.assertEqual(comp['norm_rf'], 0.0) 1118 self.assertEqual(comp['rf'], 0.0) 1119 self.assertEqual(comp['max_rf'], 2) 1120 self.assertEqual(comp['source_subtrees'], 4) 1121 1122 # test polytomy corrections 1123 1124 ref2 = Tree("((a:1, (b:1, c:1, d:1):1):1, (e:1, f:1, g:1):1);") 1125 gtree = Tree("((a:1, (b:1, (c:1, d:1):1):1), (e:1, (f:1, g:1):1):1);") 1126 1127 # Basic polytomy 1128 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref2) 1129 self.assertEqual(rf, 2) 1130 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref2, expand_polytomies=True) 1131 self.assertEqual(rf, 0) 1132 1133 1134 # nested polytomies 1135 gtree = Tree('((g, h), (a, (b, (c, (d,( e, f))))));') 1136 ref3 = Tree('((a, b, c, (d, e, f)), (g, h));') 1137 ref4 = Tree('((a, b, c, d, e, f), (g, h));') 1138 ref5 = Tree('((a, b, (c, d, (e, f))), (g, h));') 1139 1140 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref3) 1141 self.assertEqual(rf, 3) 1142 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref3, expand_polytomies=True) 1143 self.assertEqual(rf, 0) 1144 1145 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref4) 1146 self.assertEqual(rf, 4) 1147 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref4, expand_polytomies=True, 1148 polytomy_size_limit=6) 1149 self.assertEqual(rf, 0) 1150 1151 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref5) 1152 self.assertEqual(rf, 2) 1153 rf, max_rf, names, r1, r2, d1, d2 = gtree.robinson_foulds(ref5, expand_polytomies=True) 1154 self.assertEqual(rf, 0) 1155 1156 # two side polytomies 1157 t1 = Tree("((a:1, (b:1, c:1, d:1):1):1, (e:1, f:1, g:1):1);") 1158 t2 = Tree("((a:1, (b:1, c:1, d:1):1), (e:1, (f:1, g:1):1):1);") 1159 rf, max_rf, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, expand_polytomies=True) 1160 self.assertEqual(rf, 0) 1161 1162 1163 # test auto pruned tree topology 1164 for RF, unrooted, nw1, nw2 in samples: 1165 # Add fake tips in the newick 1166 for x in "clanger": 1167 nw1 = nw1.replace(x, "(%s,%s1)" %(x, x) ) 1168 nw2 = nw2.replace(x, "(%s,%s2)" %(x, x) ) 1169 t1 = Tree(nw1) 1170 t2 = Tree(nw2) 1171 rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted) 1172 self.assertEqual(len(names), 20) 1173 real_max = (20*2) - 4 if not unrooted else (20*2) - 6 1174 self.assertEqual(rf_max, real_max) 1175 self.assertEqual(rf, RF) 1176 1177 #print 'Testing RF with branch support thresholds...' 1178 # test discarding lowly supported branches 1179 for RF, unrooted, nw1, nw2 in samples: 1180 # Add fake internal nodes with low support 1181 for x in "jlnqr": 1182 nw1 = nw1.replace(x, "(%s,(%s1, %s11)0.6)" %(x, x, x) ) 1183 nw2 = nw2.replace(x, "(%s,(%s1, %s11)0.5)" %(x, x, x) ) 1184 t1 = Tree(nw1) 1185 t2 = Tree(nw2) 1186 rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted, 1187 min_support_t1 = 0.1, min_support_t2 = 0.1) 1188 self.assertEqual(len(names), 30) 1189 real_max = (30*2) - 4 if not unrooted else (30*2) - 6 1190 self.assertEqual(rf_max, real_max) 1191 self.assertEqual(rf, RF) 1192 1193 rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted, 1194 min_support_t1 = 0.0, min_support_t2 = 0.51) 1195 self.assertEqual(len(names), 30) 1196 real_max = (30*2) - 4 - 5 if not unrooted else (30*2) - 6 -5 # -5 to discount low support branches 1197 self.assertEqual(rf_max, real_max) 1198 self.assertEqual(rf, RF) 1199 1200 rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted, 1201 min_support_t1 = 0.61, min_support_t2 = 0.0) 1202 self.assertEqual(len(names), 30) 1203 real_max = (30*2) - 4 - 5 if not unrooted else (30*2) - 6 -5 # -5 to discount low support branches 1204 self.assertEqual(rf_max, real_max) 1205 self.assertEqual(rf, RF) 1206 1207 1208 rf, rf_max, names, r1, r2, d1, d2 = t1.robinson_foulds(t2, unrooted_trees=unrooted, 1209 min_support_t1 = 0.61, min_support_t2 = 0.51) 1210 self.assertEqual(len(names), 30) 1211 real_max = (30*2) - 4 - 10 if not unrooted else (30*2) - 6 -10 # -10 to discount low support branches 1212 self.assertEqual(rf_max, real_max) 1213 self.assertEqual(rf, RF) 1214 1215 1216 1217 1218 1219 def test_monophyly(self): 1220 #print 'Testing monophyly checks...' 1221 t = Tree("((((((a, e), i), o),h), u), ((f, g), j));") 1222 is_mono, monotype, extra = t.check_monophyly(values=["a", "e", "i", "o", "u"], target_attr="name") 1223 self.assertEqual(is_mono, False) 1224 self.assertEqual(monotype, "polyphyletic") 1225 is_mono, monotype, extra= t.check_monophyly(values=["a", "e", "i", "o"], target_attr="name") 1226 self.assertEqual(is_mono, True) 1227 self.assertEqual(monotype, "monophyletic") 1228 is_mono, monotype, extra = t.check_monophyly(values=["i", "o"], target_attr="name") 1229 self.assertEqual(is_mono, False) 1230 self.assertEqual(monotype, "paraphyletic") 1231 1232 # Test examples 1233 #print 'Testing monophyly check with unrooted trees' 1234 t = PhyloTree('(aaa1, (aaa3, (aaa4, (bbb1, bbb2))));') 1235 is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True) 1236 self.assertEqual(is_mono, True) 1237 self.assertEqual(extra, set()) 1238 1239 t = PhyloTree('(aaa1, (bbb3, (aaa4, (bbb1, bbb2))));') 1240 is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True) 1241 self.assertEqual(is_mono, False) 1242 self.assertEqual(extra, set([t&'bbb3'])) 1243 1244 t = PhyloTree('(aaa1, (aaa3, (aaa4, (bbb1, bbb2))));') 1245 is_mono, montype, extra = t.check_monophyly(values=set(['bbb']), target_attr='species', unrooted=True) 1246 self.assertEqual(is_mono, True) 1247 self.assertEqual(extra, set()) 1248 1249 t = PhyloTree('(aaa1, (aaa3, (aaa4, (bbb1, ccc2))));') 1250 is_mono, montype, extra = t.check_monophyly(values=set(['bbb', 'ccc']), target_attr='species', unrooted=True) 1251 self.assertEqual(is_mono, True) 1252 self.assertEqual(extra, set()) 1253 1254 t = PhyloTree('(aaa1, (aaa3, (bbb4, (bbb1, bbb2))));') 1255 is_mono, montype, extra = t.check_monophyly(values=set(['bbb4', 'bbb2']), target_attr='name', unrooted=True) 1256 self.assertEqual(is_mono, False) 1257 self.assertEqual(extra, set([t&'bbb1'])) 1258 1259 t = PhyloTree('(aaa1, (aaa3, (bbb4, (bbb1, bbb2))));') 1260 is_mono, montype, extra = t.check_monophyly(values=set(['bbb1', 'bbb2']), target_attr='name', unrooted=True) 1261 self.assertEqual(is_mono, True) 1262 self.assertEqual(extra, set()) 1263 1264 t = PhyloTree('(aaa1, aaa3, (aaa4, (bbb1, bbb2)));') 1265 is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True) 1266 self.assertEqual(is_mono, True) 1267 self.assertEqual(extra, set()) 1268 1269 t = PhyloTree('(aaa1, bbb3, (aaa4, (bbb1, bbb2)));') 1270 is_mono, montype, extra = t.check_monophyly(values=set(['aaa']), target_attr='species', unrooted=True) 1271 self.assertEqual(is_mono, False) 1272 self.assertEqual(extra, set([t&'bbb3'])) 1273 1274 #print 'Check monophyly randomization test' 1275 t = PhyloTree() 1276 t.populate(100) 1277 ancestor = t.get_common_ancestor(['aaaaaaaaaa', 'aaaaaaaaab', 'aaaaaaaaac']) 1278 all_nodes = t.get_descendants() 1279 # I test every possible node as root for the tree. The content of ancestor 1280 # should allways be detected as monophyletic 1281 results = set() 1282 for x in all_nodes: 1283 mono, part, extra = t.check_monophyly(values=set(ancestor.get_leaf_names()), target_attr='name', unrooted=True) 1284 results.add(mono) 1285 t.set_outgroup(x) 1286 self.assertEqual(list(results), [True]) 1287 1288 #print 'Testing get_monophyly' 1289 t = Tree("((((((4, e), i)M1, o),h), u), ((3, 4), (i, june))M2);", format=1) 1290 # we annotate the tree using external data 1291 colors = {"a":"red", "e":"green", "i":"yellow", 1292 "o":"black", "u":"purple", "4":"green", 1293 "3":"yellow", "1":"white", "5":"red", 1294 "june":"yellow"} 1295 for leaf in t: 1296 leaf.add_features(color=colors.get(leaf.name, "none")) 1297 green_yellow_nodes = set([t&"M1", t&"M2"]) 1298 mono_nodes = t.get_monophyletic(values=["green", "yellow"], target_attr="color") 1299 self.assertEqual(set(mono_nodes), green_yellow_nodes) 1300 1301 1302 def test_copy(self): 1303 t = Tree("((A, B)Internal_1:0.7, (C, D)Internal_2:0.5)root:1.3;", format=1) 1304 # we add a custom annotation to the node named A 1305 (t & "A").add_features(label="custom Value") 1306 # we add a complex feature to the A node, consisting of a list of lists 1307 (t & "A").add_features(complex=[[0,1], [2,3], [1,11], [1,0]]) 1308 1309 1310 t_nw = t.copy("newick") 1311 t_nwx = t.copy("newick-extended") 1312 t_pkl = t.copy("cpickle") 1313 (t & "A").testfn = lambda: "YES" 1314 t_deep = t.copy("deepcopy") 1315 1316 self.assertEqual((t_nw & "root").name, "root") 1317 self.assertEqual((t_nwx & "A").label, "custom Value") 1318 self.assertEqual((t_pkl & "A").complex[0], [0,1]) 1319 self.assertEqual((t_deep & "A").testfn(), "YES") 1320 1321 1322 def test_cophenetic_matrix(self): 1323 t = Tree(nw_full) 1324 dists, leaves = t.cophenetic_matrix() 1325 actualdists = [ 1326 [0, 2.3662779999999994, 2.350554999999999, 2.7002369999999996, 3.527812, 3.305472, 2.424086, 2.424086, 1327 2.432288, 2.483421, 2.3355079999999995, 2.3355079999999995, 2.389350999999999, 2.3812519999999995, 1328 2.404005999999999, 2.3945459999999996, 2.4035289999999994, 2.3689599999999995, 2.4048339999999997, 1329 2.6487609999999995], 1330 [2.3662779999999994, 0, 0.079009, 1.122461, 2.38897, 2.16663, 0.47755000000000003, 0.47755000000000003, 1331 0.4857520000000001, 0.5368850000000001, 0.320202, 0.32020200000000004, 0.133729, 0.12563, 1332 0.14838400000000002, 0.230406, 0.168047, 0.113338, 0.16935199999999997, 0.633455], 1333 [2.350554999999999, 0.079009, 0, 1.106738, 2.373247, 2.150907, 0.461827, 0.461827, 0.47002900000000003, 1334 0.521162, 0.304479, 0.30447900000000006, 0.11800599999999999, 0.10990699999999998, 0.132661, 0.214683, 1335 0.152324, 0.09761499999999998, 0.153629, 0.617732], 1336 [2.7002369999999996, 1.122461, 1.106738, 0, 2.7229289999999997, 2.5005889999999997, 1.180269, 1.180269, 1337 1.188471, 1.239604, 1.091691, 1.091691, 1.145534, 1.137435, 1.160189, 1.1507290000000001, 1.159712, 1338 1.125143, 1.161017, 1.404944], 1339 [3.527812, 2.38897, 2.373247, 2.7229289999999997, 0, 2.6926, 2.446778, 2.446778, 2.45498, 2.506113, 1340 2.3581999999999996, 2.3581999999999996, 2.412043, 2.403944, 2.426698, 2.4172379999999998, 1341 2.4262209999999995, 2.391652, 2.427526, 2.6714529999999996], 1342 [3.305472, 2.16663, 2.150907, 2.5005889999999997, 2.6926, 0, 2.224438, 2.224438, 2.23264, 2.283773, 2.13586, 1343 2.13586, 2.189703, 2.181604, 2.204358, 2.194898, 2.2038809999999995, 2.169312, 2.205186, 2.449113], 1344 [2.424086, 0.47755000000000003, 0.461827, 1.180269, 2.446778, 2.224438, 0, 0.0, 0.01366, 1345 0.30963300000000005, 0.44678, 0.44677999999999995, 0.5006229999999999, 0.49252399999999996, 0.515278, 1346 0.505818, 0.5148010000000001, 0.480232, 0.5161060000000001, 0.7600329999999998], 1347 [2.424086, 0.47755000000000003, 0.461827, 1.180269, 2.446778, 2.224438, 0.0, 0, 0.01366, 1348 0.30963300000000005, 0.44678, 0.44677999999999995, 0.5006229999999999, 0.49252399999999996, 0.515278, 1349 0.505818, 0.5148010000000001, 0.480232, 0.5161060000000001, 0.7600329999999998], 1350 [2.432288, 0.4857520000000001, 0.47002900000000003, 1.188471, 2.45498, 2.23264, 0.01366, 0.01366, 0, 1351 0.317835, 0.45498200000000005, 0.454982, 0.508825, 0.500726, 0.5234800000000001, 0.51402, 0.523003, 1352 0.48843400000000003, 0.524308, 0.7682349999999999], 1353 [2.483421, 0.5368850000000001, 0.521162, 1.239604, 2.506113, 2.283773, 0.30963300000000005, 1354 0.30963300000000005, 0.317835, 0, 0.506115, 0.506115, 0.559958, 0.551859, 0.574613, 0.565153, 0.574136, 1355 0.539567, 0.5754410000000001, 0.8193679999999999], 1356 [2.3355079999999995, 0.320202, 0.304479, 1.091691, 2.3581999999999996, 2.13586, 0.44678, 0.44678, 1357 0.45498200000000005, 0.506115, 0, 0.0, 0.343275, 0.33517600000000003, 0.35793, 0.34847, 1358 0.35745299999999997, 0.322884, 0.35875799999999997, 0.531709], 1359 [2.3355079999999995, 0.32020200000000004, 0.30447900000000006, 1.091691, 2.3581999999999996, 2.13586, 1360 0.44677999999999995, 0.44677999999999995, 0.454982, 0.506115, 0.0, 0, 0.34327500000000005, 1361 0.33517600000000003, 0.35793, 0.34847, 0.357453, 0.32288400000000006, 0.358758, 0.531709], 1362 [2.389350999999999, 0.133729, 0.11800599999999999, 1.145534, 2.412043, 2.189703, 0.5006229999999999, 1363 0.5006229999999999, 0.508825, 0.559958, 0.343275, 0.34327500000000005, 0, 0.013558999999999998, 0.021967, 1364 0.25347900000000007, 0.19112, 0.031257, 0.192425, 0.656528], 1365 [2.3812519999999995, 0.12563, 0.10990699999999998, 1.137435, 2.403944, 2.181604, 0.49252399999999996, 1366 0.49252399999999996, 0.500726, 0.551859, 0.33517600000000003, 0.33517600000000003, 0.013558999999999998, 0, 1367 0.028214, 0.24538000000000004, 0.183021, 0.023157999999999998, 0.184326, 0.648429], 1368 [2.404005999999999, 0.14838400000000002, 0.132661, 1.160189, 2.426698, 2.204358, 0.515278, 0.515278, 1369 0.5234800000000001, 0.574613, 0.35793, 0.35793, 0.021967, 0.028214, 0, 0.26813400000000004, 1370 0.20577499999999999, 0.045912, 0.20708, 0.6711830000000001], 1371 [2.3945459999999996, 0.230406, 0.214683, 1.1507290000000001, 2.4172379999999998, 2.194898, 0.505818, 1372 0.505818, 0.51402, 0.565153, 0.34847, 0.34847, 0.25347900000000007, 0.24538000000000004, 1373 0.26813400000000004, 0, 0.267657, 0.233088, 0.268962, 0.661723], 1374 [2.4035289999999994, 0.168047, 0.152324, 1.159712, 2.4262209999999995, 2.2038809999999995, 1375 0.5148010000000001, 0.5148010000000001, 0.523003, 0.574136, 0.35745299999999997, 0.357453, 0.19112, 1376 0.183021, 0.20577499999999999, 0.267657, 0, 0.170729, 0.057269, 0.670706], 1377 [2.3689599999999995, 0.113338, 0.09761499999999998, 1.125143, 2.391652, 2.169312, 0.480232, 0.480232, 1378 0.48843400000000003, 0.539567, 0.322884, 0.32288400000000006, 0.031257, 0.023157999999999998, 0.045912, 1379 0.233088, 0.170729, 0, 0.17203399999999996, 0.636137], 1380 [2.4048339999999997, 0.16935199999999997, 0.153629, 1.161017, 2.427526, 2.205186, 0.5161060000000001, 1381 0.5161060000000001, 0.524308, 0.5754410000000001, 0.35875799999999997, 0.358758, 0.192425, 0.184326, 1382 0.20708, 0.268962, 0.057269, 0.17203399999999996, 0, 0.672011], 1383 [2.6487609999999995, 0.633455, 0.617732, 1.404944, 2.6714529999999996, 2.449113, 0.7600329999999998, 1384 0.7600329999999998, 0.7682349999999999, 0.8193679999999999, 0.531709, 0.531709, 0.656528, 0.648429, 1385 0.6711830000000001, 0.661723, 0.670706, 0.636137, 0.672011, 0] 1386 ] 1387 1388 actualleaves = ['Aga0007658', 'Bta0018700', 'Cfa0016700', 'Cin0011239', 'Ddi0002240', 'Dme0014628', 1389 'Dre0008390', 'Dre0008391', 'Dre0008392', 'Fru0004507', 'Gga0000981', 'Gga0000982', 1390 'Hsa0000001', 'Hsa0010711', 'Hsa0010730', 'Mdo0014718', 'Mms0024821', 'Ptr0000001', 1391 'Rno0030248', 'Xtr0044988'] 1392 1393 for i in range(len(actualdists)): 1394 for j in range(len(actualdists[i])): 1395 self.assertAlmostEqual(actualdists[i][j], dists[i][j], places=4) 1396 self.assertEqual(actualleaves, leaves) 1397 1398 1399 # def test_traversing_speed(self): 1400 # return 1401 # for x in xrange(10): 1402 # t = Tree() 1403 # t.populate(100000) 1404 1405 # leaves = t.get_leaves() 1406 # sample = random.sample(leaves, 100) 1407 1408 # t1 = time.time() 1409 # a = t.get_common_ancestor_OLD(sample) 1410 # t2 = time.time() - t1 1411 # print "OLD get common", t2 1412 1413 # t1 = time.time() 1414 # b = t.get_common_ancestor(sample) 1415 # t2 = time.time() - t1 1416 # print "NEW get common", t2 1417 1418 # self.assertEqual(a, b) 1419 1420 1421 # t1 = time.time() 1422 # [n for n in t._iter_descendants_postorder_OLD()] 1423 # t2 = time.time() - t1 1424 # print "OLD postorder", t2 1425 1426 # t1 = time.time() 1427 # [n for n in t._iter_descendants_postorder()] 1428 # t2 = time.time() - t1 1429 # print "NEW postorder", t2 1430 1431if __name__ == '__main__': 1432 unittest.main() 1433