annotate commons/core/tree/Tree.py @ 14:c79b9ae3f65f

Deleted selected files
author m-zytnicki
date Fri, 19 Apr 2013 10:13:11 -0400
parents 769e306b7933
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
1 import os, re, sys
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
2
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
3 class Tree:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
4
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
5 def __init__( self, inFileName="" ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
6 self.tree = None
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
7 self.inFileName = inFileName
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
8 if self.inFileName != "":
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
9 self.loadTree()
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
10
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
11 def loadTree( self, verbose=0 ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
12 inF = open( self.inFileName, "r" )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
13 lines = inF.readlines()
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
14 inF.close()
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
15 line = "".join(lines).replace("\n","")
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
16 self.tree = self.parseTree( line )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
17 if verbose > 0:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
18 print "nb of leaves: %i" % ( self.getNbOfLeaves( self.tree ) )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
19
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
20 def parseTree( self, sTree ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
21 if "," not in sTree:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
22 name, length = sTree.split(":")
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
23 return self.makeLeaf( name, float(length) )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
24
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
25 distPattern = re.compile(r'(?P<tree>\(.+\))\:(?P<length>[e\-\d\.]+)$')
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
26 m = distPattern.search( sTree )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
27 length = 0
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
28 if m:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
29 if m.group('length'): length = float( m.group('length') )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
30 sTree = m.group('tree')
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
31 if length == "": length = 0
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
32
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
33 lhs, rhs = self.parseSubTree( sTree )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
34
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
35 return { "name": "internal",
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
36 "left": self.parseTree( lhs ),
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
37 "right": self.parseTree( rhs ),
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
38 "length": length }
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
39
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
40 def makeLeaf( self, name, length ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
41 return { "left":None, "right":None, "name":name, "length":length }
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
42
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
43 def parseSubTree( self, sTree ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
44 """
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
45 Parse a newick-formatted string of type 'a,b' into [a,b]
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
46 """
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
47 chars = list( sTree[1:-1] )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
48 count = 0
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
49 isLhs = True
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
50 leftS = ""
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
51 rightS = ""
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
52 for c in chars:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
53 if c == "(":
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
54 count += 1
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
55 elif c == ")":
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
56 count -= 1
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
57 elif (c == ",") and (count == 0) and (isLhs) :
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
58 isLhs = False
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
59 continue
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
60 if isLhs: leftS += c
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
61 else: rightS += c
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
62 return [ leftS, rightS ]
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
63
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
64 def toNewick( self, tree ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
65 newString = ""
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
66 if tree["name"] is not "internal":
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
67 newString += tree["name"]
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
68 else:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
69 newString += "("
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
70 newString += self.toNewick( tree["left"] )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
71 newString += ","
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
72 newString += self.toNewick( tree["right"] )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
73 newString += ")"
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
74 if tree["length"]:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
75 newString += ":"
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
76 newString += "%f" % ( tree["length"] )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
77 return newString
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
78
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
79 def saveTree( self, outFileName ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
80 outF = open( outFileName, "w" )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
81 outF.write( self.toNewick( self.tree ) )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
82 outF.close()
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
83
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
84 def replaceHeaderViaPrefixSearch( self, tree, dNew2Init ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
85 if dNew2Init.has_key( tree["name"] ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
86 tree["name"] = dNew2Init[ tree["name"] ].replace(" ","_").replace("::","-").replace(",","-")
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
87 if tree["left"] != None:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
88 self.replaceHeaderViaPrefixSearch( tree["left"], dNew2Init )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
89 if tree["right"] != None:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
90 self.replaceHeaderViaPrefixSearch( tree["right"], dNew2Init )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
91
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
92 def retrieveInitialSequenceHeaders( self, dNew2Init, outFileName ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
93 tree = self.tree
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
94 self.replaceHeaderViaPrefixSearch( tree, dNew2Init )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
95 self.tree = tree
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
96 self.saveTree( outFileName )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
97
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
98 def getNbOfChildNodes( self, tree, nbNodes ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
99 if tree["left"] is not None:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
100 nbNodes += 1
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
101 nbNodes = self.getNbOfChildNodes( tree["left"], nbNodes )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
102 if tree["right"] is not None:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
103 nbNodes += 1
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
104 nbNodes = self.getNbOfChildNodes( tree["right"], nbNodes )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
105 return nbNodes
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
106
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
107 def getNbOfNodes( self ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
108 nbNodes = 0
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
109 return self.getNbOfChildNodes( self.tree, nbNodes )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
110
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
111 def getNbOfChildLeaves( self, tree, nbLeaves ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
112 if tree["name"] != "internal":
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
113 nbLeaves += 1
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
114 if tree["left"] is not None:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
115 nbLeaves = self.getNbOfChildLeaves( tree["left"], nbLeaves )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
116 if tree["right"] is not None:
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
117 nbLeaves = self.getNbOfChildLeaves( tree["right"], nbLeaves )
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
118 return nbLeaves
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
119
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
120 def getNbOfLeaves( self ):
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
121 nbLeaves = 0
769e306b7933 Change the repository level.
yufei-luo
parents:
diff changeset
122 return self.getNbOfChildLeaves( self.tree, nbLeaves )