Use Python to extract Branch Lengths from Newick Format

Question

I have a list in python consisting of one item which is a tree written in Newick Format, as below:

['(BMNH833953:0.16529463651919140688,(((BMNH833883:0.22945757727367316336,(BMNH724182a:0.18028180766761139897,(BMNH724182b:0.21469677818346077913,BMNH724082:0.54350916483644962085):0.00654573856803835914):0.04530853441176059537):0.02416511342888815264,(((BMNH794142:0.21236619242575086042,(BMNH743008:0.13421900772403019819,BMNH724591:0.14957653992840658219):0.02592135486124686958):0.02477670174791116522,BMNH703458a:0.22983459269245612444):0.00000328449424529074,BMNH703458b:0.29776257618061197086):0.09881729077887969892):0.02257522897558370684,BMNH833928:0.21599133163597591945):0.02365043128986757739,BMNH724053:0.16069861523756587274):0.0;']

In tree format this appears as below:

I am trying to write some code that will look through the list item and return the IDs (BMNHxxxxxx) which are joined by branch length of 0 (or <0.001 for example) (highlighted in red). I thought about using regex such as:

JustTree = []
with JustTree as f:
    for match in re.finditer(r"(?<=Item\sA)(?:(?!Item\sB).){50,}", subject, re.I):
        f.extend(match.group()+"\n") 

As taken from another StackOverflow answer where item A would be a ':' as the branch lengths always appear after a : and item B would be either a ',' or ')'or a ';' as these a there three characters that delimit it, but Im not experienced enough in regex to do this.

By using a branch length of 0 in this case I want the code to output ['BMNH703458a', 'BMNH703458b']. If I could alter this to also include ID's joined by a branch length of user defined value of say 0.01 this would be highly useful.

If anyone has any input, or can point me to a useful answer I would highly appreciate it.

Answer 1

Okay, here's a regex to extract only numbers (with potential decimals):

\b[0-9]+(?:\.[0-9]+)?\b

The \bs make sure that there is no other number, letter or underscore around the number right next to it. It's called a word boundary.

[0-9]+ matches multiple digits.

(?:\.[0-9]+)? is an optional group, meaning that it may or may not match. If there is a dot and digits after the first [0-9]+, then it will match those. Otherwise, it won't. The group itself matches a dot, and at least 1 digit.

You can use it with re.findall to put all the matches in a list:

import re
NewickTree = ['(BMNH833953:0.16529463651919140688,(((BMNH833883:0.22945757727367316336,(BMNH724182a:0.18028180766761139897,(BMNH724182b:0.21469677818346077913,BMNH724082:0.54350916483644962085):0.00654573856803835914):0.04530853441176059537):0.02416511342888815264,(((BMNH794142:0.21236619242575086042,(BMNH743008:0.13421900772403019819,BMNH724591:0.14957653992840658219):0.02592135486124686958):0.02477670174791116522,BMNH703458a:0.22983459269245612444):0.00000328449424529074,BMNH703458b:0.29776257618061197086):0.09881729077887969892):0.02257522897558370684,BMNH833928:0.21599133163597591945):0.02365043128986757739,BMNH724053:0.16069861523756587274):0.0;']

pattern = re.compile(r"\b[0-9]+(?:\.[0-9]+)?\b")

for tree in NewickTree:
    branch_lengths = pattern.findall(tree)
    # Do stuff to the list branch_lengths
    print(branch_lengths)

For this list, you get this printed:

['0.16529463651919140688', '0.22945757727367316336', '0.18028180766761139897',
 '0.21469677818346077913', '0.54350916483644962085', '0.00654573856803835914', 
 '0.04530853441176059537', '0.02416511342888815264', '0.21236619242575086042',
 '0.13421900772403019819', '0.14957653992840658219', '0.02592135486124686958', 
 '0.02477670174791116522', '0.22983459269245612444', '0.00000328449424529074',
 '0.29776257618061197086', '0.09881729077887969892', '0.02257522897558370684',
 '0.21599133163597591945', '0.02365043128986757739', '0.16069861523756587274',
 '0.0']

Answer 2

I know your question has been answered, but if you ever want your data as a nested list instead of a flat string:

import re
import pprint

a="(BMNH833953:0.16529463651919140688,(((BMNH833883:0.22945757727367316336,(BMNH724182a:0.18028180766761139897,(BMNH724182b:0.21469677818346077913,BMNH724082:0.54350916483644962085):0.00654573856803835914):0.04530853441176059537):0.02416511342888815264,(((BMNH794142:0.21236619242575086042,(BMNH743008:0.13421900772403019819,BMNH724591:0.14957653992840658219):0.02592135486124686958):0.02477670174791116522,BMNH703458a:0.22983459269245612444):0.00000328449424529074,BMNH703458b:0.29776257618061197086):0.09881729077887969892):0.02257522897558370684,BMNH833928:0.21599133163597591945):0.02365043128986757739,BMNH724053:0.16069861523756587274):0.0;"

def tokenize(str):
  for m in re.finditer(r"\(|\)|[\w.:]+", str):
    yield m.group()

def make_nested_list(tok, L=None):
  if L is None: L = []
  while True:
    try: t = tok.next()
    except StopIteration: break
    if   t == "(": L.append(make_nested_list(tok))
    elif t == ")": break
    else:
      i = t.find(":"); assert i != -1
      if i == 0: L.append(float(t[1:]))
      else:      L.append([t[:i], float(t[i+1:])])
  return L

L = make_nested_list(tokenize(a))
pprint.pprint(L)

Answer 3

There are several Python libraries that support the newick format. The ETE toolkit allows to read newick strings and operate with trees as Python objects:

from ete2 import Tree
tree = Tree(newickFile)
print tree

Several newick subformats can be choosen and branch distances are parsed even if they are expressed in scientific notation.

from ete2 import Tree
tree = Tree("(A:3.4, (B:0.15E-10,C:0.0001):1.5E-234);")