Generate Binary Tree From String

Recently while implementing the Small Parsimony Problem I had the need to generate a binary tree from a string in Python.

The pseudo-code in the question implicitly assumes you have some functionality that will generate a DNA sequence like CAAATCCC into a binary tree, then run SmallParsimony on it. I couldn’t find that functionality anywhere, so I decided to implement something simple in networkx. Hopefully it’s useful.

#!/usr/bin/env python
“””
Shane Dowling, 27 Oct 2015
To run simply call generate_leaf_graph and pass in s string.
“””
def count_predecessors(T):
pred = 0
for v in T.nodes():
pred += 1
return pred
def generate_leaf_graph(s):
“””
Will generate a leaf graph and return it along
with the Character dictionary representing the characters
at each leaf node position
“””
T = nx.DiGraph()
Character = {}
i = 0
parI = len(s)
for (son, daughter) in zip(s[0::2], s[1::2]):
Character[i] = son
Character[i+1] = daughter
T.add_edge(parI, i)
T.add_edge(parI, i+1)
i += 2
parI += 1
while count_predecessors(T) > 1:
for v in T.nodes():
T.add_edge(parI, v)
T.add_edge(parI, v+1)
parI += 1
return [T, Character]