1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
#!/usr/bin/python3
import sys, re, json, sqlite3
import os.path
usageInfo = f"usage: {sys.argv[0]}\n"
usageInfo += "Reads labelled_supertree_ottnames.tre & annotations.json (from an Open Tree of Life release), \n"
usageInfo += "and creates a sqlite database, which holds entries of the form (name text, data text).\n"
usageInfo += "Each row holds a tree-of-life node's name, JSON-encoded child name array, a parent name or '', \n"
usageInfo += "number of descendant 'tips', and a 1 or 0 indicating phylogenetic-support.\n"
usageInfo += "\n"
usageInfo += "Expected labelled_supertree_ottnames.tre format:\n"
usageInfo += " Represents a tree-of-life in Newick format, roughly like (n1,n2,(n3,n4)n5)n6,\n"
usageInfo += " where root node is named n6, and has children n1, n2, and n5.\n"
usageInfo += " Name forms include Homo_sapiens_ott770315, mrcaott6ott22687, and 'Oxalis san-miguelii ott5748753'\n"
usageInfo += " Some names can be split up into a 'simple' name (like Homo_sapiens) and an id (like ott770315)\n"
usageInfo += "Expected annotations.json format:\n"
usageInfo += " JSON object holding information about the tree-of-life release.\n"
usageInfo += " The object's 'nodes' field maps node IDs to objects holding information about that node,\n"
usageInfo += " such as phylogenetic trees that support/conflict with it's placement.\n"
if len(sys.argv) > 1:
print(usageInfo, file=sys.stderr)
sys.exit(1)
treeFile = "otol/labelled_supertree_ottnames.tre"
annFile = "otol/annotations.json"
dbFile = "data.db"
nodeMap = {} # Maps node names to node objects
idToName = {} # Maps node IDs to names
# Check for existing db
if os.path.exists(dbFile):
print("ERROR: Existing {} db".format(dbFile), file=sys.stderr)
sys.exit(1)
# Parse treeFile
data = None
with open(treeFile) as file:
data = file.read()
dataIdx = 0
def parseNewick():
"""Parses a node using 'data' and 'dataIdx', updates nodeMap accordingly, and returns the node name or None"""
global dataIdx
# Check for EOF
if dataIdx == len(data):
print("ERROR: Unexpected EOF at index " + str(dataIdx), file=sys.stderr)
return None
# Check for node
if data[dataIdx] == "(": # parse inner node
dataIdx += 1
childNames = []
while True:
# Read child
childName = parseNewick()
if childName == None:
return None
childNames.append(childName)
if (dataIdx == len(data)):
print("ERROR: Unexpected EOF", file=sys.stderr)
return None
# Check for next child
if (data[dataIdx] == ","):
dataIdx += 1
continue
else:
# Get node name
dataIdx += 1 # Consume an expected ')'
[name, id] = parseNewickName()
idToName[id] = name
# Get child num-tips total
tips = 0
for childName in childNames:
tips += nodeMap[childName]["tips"]
# Add node to nodeMap
if name in nodeMap: # Turns out the names might not actually be unique
count = 2
name2 = name + " [" + str(count) + "]"
while name2 in nodeMap:
count += 1
name2 = name + " [" + str(count) + "]"
name = name2
nodeMap[name] = {
"name": name, "id": id, "children": childNames, "parent": None, "tips": tips, "pSupport": False
}
# Update childrens' parent reference
for childName in childNames:
nodeMap[childName]["parent"] = name
return name
else: # Parse node name
[name, id] = parseNewickName()
idToName[id] = name
nodeMap[name] = {"name": name, "id": id, "children": [], "parent": None, "tips": 1, "pSupport": False}
return name
def parseNewickName():
"""Helper that parses an input node name, and returns a [name,id] pair"""
global data, dataIdx
name = None
end = dataIdx
# Get name
if (end < len(data) and data[end] == "'"): # Check for quoted name
end += 1
inQuote = True
while end < len(data):
if (data[end] == "'"):
if end + 1 < len(data) and data[end+1] == "'": # Account for '' as escaped-quote
end += 2
continue
else:
end += 1
inQuote = False
break
end += 1
if inQuote:
raise Exception("ERROR: Unexpected EOF")
name = data[dataIdx:end]
dataIdx = end
else:
while end < len(data) and not re.match(r"[(),]", data[end]):
end += 1
if (end == dataIdx):
raise Exception("ERROR: Unexpected EOF")
name = data[dataIdx:end].rstrip()
if end == len(data): # Ignore trailing input semicolon
name = name[:-1]
dataIdx = end
# Convert to [name, id]
name = name.lower()
if name.startswith("mrca"):
return [name, name]
elif name[0] == "'":
match = re.fullmatch(r"'([^\\\"]+) (ott\d+)'", name)
if match == None:
raise Exception("ERROR: invalid name \"{}\"".format(name))
name = match.group(1).replace("''", "'")
return [name, match.group(2)]
else:
match = re.fullmatch(r"([^\\\"]+)_(ott\d+)", name)
if match == None:
raise Exception("ERROR: invalid name \"{}\"".format(name))
return [match.group(1).replace("_", " "), match.group(2)]
rootName = parseNewick()
# Parse annFile
data = None
with open(annFile) as file:
data = file.read()
obj = json.loads(data)
nodeAnnsMap = obj['nodes']
# Change mrca* names
def applyMrcaNameConvert(name, namesToSwap):
"""
Given an mrca* name, makes namesToSwap map it to an expanded version with the form [childName1 + childName2].
May recurse on child nodes with mrca* names.
Also returns the name of the highest-tips child (used when recursing).
"""
node = nodeMap[name]
childNames = node["children"]
if len(childNames) < 2:
print("WARNING: MRCA node \"{}\" has less than 2 children".format(name), file=sys.stderr)
return name
# Get 2 children with most tips
childTips = []
for n in childNames:
childTips.append(nodeMap[n]["tips"])
maxTips = max(childTips)
maxIdx = childTips.index(maxTips)
childTips[maxIdx] = 0
maxTips2 = max(childTips)
maxIdx2 = childTips.index(maxTips2)
childName1 = node["children"][maxIdx]
childName2 = node["children"][maxIdx2]
# Check for composite child names
if childName1.startswith("mrca"):
childName1 = applyMrcaNameConvert(childName1, namesToSwap)
if childName2.startswith("mrca"):
childName2 = applyMrcaNameConvert(childName2, namesToSwap)
# Create composite name
namesToSwap[name] = "[{} + {}]".format(childName1, childName2)
return childName1
namesToSwap = {} # Maps mrca* names to replacement names
for node in nodeMap.values():
name = node["name"]
if (name.startswith("mrca") and name not in namesToSwap):
applyMrcaNameConvert(name, namesToSwap)
for [oldName, newName] in namesToSwap.items():
nodeMap[newName] = nodeMap[oldName]
del nodeMap[oldName]
for node in nodeMap.values():
parentName = node["parent"]
if (parentName in namesToSwap):
node["parent"] = namesToSwap[parentName]
childNames = node["children"]
for i in range(len(childNames)):
childName = childNames[i]
if (childName in namesToSwap):
childNames[i] = namesToSwap[childName]
# Add annotations data
for node in nodeMap.values():
# Set has-support value using annotations
id = node["id"]
if id in nodeAnnsMap:
nodeAnns = nodeAnnsMap[id]
supportQty = len(nodeAnns["supported_by"]) if "supported_by" in nodeAnns else 0
conflictQty = len(nodeAnns["conflicts_with"]) if "conflicts_with" in nodeAnns else 0
node["pSupport"] = supportQty > 0 and conflictQty == 0
# Root node gets support
if node["parent"] == None:
node["pSupport"] = True
# Create db
dbCon = sqlite3.connect(dbFile)
dbCur = dbCon.cursor()
dbCur.execute("CREATE TABLE nodes (name TEXT PRIMARY KEY, children TEXT, parent TEXT, tips INT, p_support INT)")
for name in nodeMap.keys():
node = nodeMap[name]
dbCur.execute("INSERT INTO nodes VALUES (?, ?, ?, ?, ?)",
(name, json.dumps(node["children"]), "" if node["parent"] == None else node["parent"],
node["tips"], 1 if node["pSupport"] else 0))
dbCon.commit()
dbCon.close()
|
