7 from random
import shuffle
10 from Bio.Align
import MultipleSeqAlignment
12 from utilities
import *
39 leaf_names = set(tree.get_leaf_names())
41 raise RuntimeError(
"Number of sequnces in alignment:\n" + repr(alignment)
42 +
"\ndoes not match the number of leaves in tree:\n" + repr(tree))
44 if seq_id
not in leaf_names:
45 raise RuntimeError(
"Sequence ID (" + seq_id
46 +
") does not match any leaf in tree:\n" + repr(tree))
70 for col_idx
in range(self._alignment.get_alignment_length()):
85 for child
in node.children:
89 for child
in node.children:
95 for child
in node.children:
151 quartet_combinations = []
152 for combination
in combination_utils.uniqueCombinationsGenerator(self._sequencesDict.keys(), 4):
153 quartet_combinations.append(combination)
167 self._tree.get_tree_root().unroot()
191 seq_ids = self._sequencesDict.keys()
194 for seq_id
in seq_ids:
195 tree.add_child(name=seq_id)
199 for step
in range(steps):
203 tree = rooted_tree.children[0]
204 tree.add_child(rooted_tree.children[1])
207 for i
in range(4,len(seq_ids)):
208 tree_utils.initEdgeLengths(tree, 0)
211 for triplet
in combination_utils.combinationsGenerator(seq_ids[0:i], 3):
212 triplet.append(seq_ids[i])
213 quartets.append(tuple(triplet))
215 qt_topos_found = set()
216 for quartet
in quartets:
219 if qt_topo_id == optimal_qt_topo_id
and qt_topo_id
not in qt_topos_found:
220 qt_topos_found.add(qt_topo_id)
224 shortest_edge = tree_utils.findShortestEdge(tree)
227 new_node.add_child(name=seq_ids[i])
228 detached = shortest_edge[1].detach()
229 shortest_edge[0].add_child(new_node)
230 new_node.add_child(detached)
233 tree_utils.initEdgeLengths(tree, 1)
237 return tree_utils.findConsensusTree(trees)
245 optimal_quartets = dict()
246 for quartet
in quartets:
248 assert quartet_id
not in optimal_quartets
253 quartet[i] = quartet[2]
257 min_cost = float(
"inf")
258 for quartet_key, tree
in trees.iteritems():
259 alignment = MultipleSeqAlignment([])
261 if record.id
in quartet:
262 alignment.append(record)
264 if small_parsimony.cost < min_cost:
265 min_cost = small_parsimony.cost
266 optimal_quartets[quartet_id] = {
267 "topology" : quartet_key
270 return optimal_quartets
288 return "".join(sorted(quartet))
308 return LargeParsimony.getQuartetID(quartet[0:2]) + LargeParsimony.getQuartetID(quartet[2:4])
322 left = root.add_child(name=
"Left")
323 left.add_child(name=quartet[0])
324 left.add_child(name=quartet[1])
325 right = root.add_child(name=
"Right")
326 right.add_child(name=quartet[2])
327 right.add_child(name=quartet[3])
328 for desc
in root.iter_descendants():
342 start_node = tree.search_nodes(name=start)[0]
343 end_node = tree.search_nodes(name=dest)[0]
348 to_visit.add(start_node)
349 node_from[start_node] =
None
351 while to_visit
and not path_found:
352 current = to_visit.pop()
353 neighbors = set(current.children)
355 neighbors.add(current.up)
356 for neighbor
in neighbors:
357 if neighbor
not in visited:
358 node_from[neighbor] = current
359 if neighbor == end_node:
363 to_visit.add(neighbor)
368 if node.name !=
"Left":
370 node = node_from[node]