Ed's Big Plans

>>> Attached: ( parse_newick.js – implementation in JS | index.html – example use ) <<<

This method of parsing works for any language that allows recursive functions — basically any of the curly bracket languages (C#, C, Java) and the fast-development languages (Ruby, JavaScript, Python) can do this. This particular example will include JavaScript code which you can take and do whatever you want with — recursive descent parsing is a well-known and solved problem, so it’s no skin off my back. Before we begin, I should probably explain what a tree in Newick format is.

What exactly is the Newick format?

Remember back in second year CS when your data structures / abstract data types / algorithms instructor said you can represent any tree as a traversal? Well, if not — don’t fret, it’s not hard to get the hang of.

A traversal is a finite, deterministic representation of a tree which can be thought of as a road map of how to visit each node of the tree exactly once. The phylogeny / bioinformatics people will know each of these nodes as either taxa / sequences (the leaves) or profiles (the internal nodes — i.e. not the leaves). A tree in Newick format is exactly that — a traversal. More specifically, it is a depth-first post-order traversal. When traversing a tree, we have a few options about how we want to visit the nodes — depth-first post-order means we want to start at the left-most, deepest leaf, and recursively visit all of the nodes before we end at the root.

A tree expressed in Newick format describes a tree as an observer has seen it having visited each node in a depth-first post-order traversal.

A node in the Newick format can be…

• A leaf in the form: “<name>:<branch_length>”
  • e.g. “lcl|86165:-0“
  • e.g. “gi|15072471:0.00759886“
  • e.g. “gi|221105210:0.00759886“
• Or a node in the form “(<node>,<node>):<branch_length>”
  • This is where it gets tricky and recursive — the “node” item above can be another node, or a leaf — when a node is composed of at least another node, we call that a recursive case; when a node is composed of only leaves, we call that a base case. We make this clearer in the next section.
• Or a node in the form “(<node>,<node>);”
  • The semi-colon at the end means that we have finished describing the tree. There is no branch length as the root of the tree is not connected to a parent.

Understanding recursion in a Newick Tree

Base case e.g.: The below node is composed of two leaves.

“(lcl|86165:-0,gi|87118305:-0):0.321158”

Recursive case e.g.: The below node is composed of a leaf on the left, and another node on the right; this right-node is composed of two leaves.

“(gi|71388322:0.0345038,(gi|221107809:0.00952396,gi|221101741:0.00952396):0.0249798):0.0111081“

If the names look a bit funny, that’s because these are sequences pulled out of a blastp search.

The Newick tree itself may have any number of nodes, the base case being a single node. The only restriction is that any node either is a leaf (has zero children) or must have two children (never a single child). These two children again are allowed to be either leaves or other nodes.

We would visualize the above Recursive case e.g. as follows.:

Where the numbers beside the edges are edge length and the names of the named taxa are indicated inside the circles (leaves). The unnamed internal nodes are the profiles that have been calculated with alignments. You’ll notice that there’s a score leading out of the root of this subtree into the rest of the tree (not shown). If this was a complete tree on its own, the root would have no score there and no arrow coming out of it.

Finally, Parsing!

Now that we have reviewed the depth-first post-order traversal, the Newick format and how to interpret it; we can move onto parsing these things. In parsing, we hope to create an in-memory structure that represents the tree. The parser I discuss assumes that the Newick format string already has had all newlines stripped, as it uses regular expressions. If your trees aren’t stored that way, just make sure that newlines are stripped before feeding it into my function. The in-memory object that’s created will have the following fields as a minimum.

• node_type left – the left child of a node
• node_type right – the right child of a node
• string_type name – the name of a node (if it is a leaf)
• float_type score – the length of the branch coming out of the top of a given node

I also use the following two fields to keep track of a few house keeping items and to make life pleasant for future tasks with this in-memory structure.

• node_type parent – the parent of a node
• integer_type serial – the order in which this node occurs when parsed

Note that in future, a depth-first post-order traversal will yield the nodes in the exact order that they were read — so in reality “this.serial” isn’t really needed, but it’s nice to have for future functions you might write as a shorthand. Have you understood why these nodes would occur in the same order?

Each language has its own quirks. Python and JavaScript have the advantage that you can define a class and define its properties (fields) on the fly — meaning there’s less code to download and to write, which is particularly good for blogs

Here’s pseudo-code for the recursive descent parsing function “tree_builder(<newick_string>)” — I don’t indicate where to strip away newlines because I assume they’re gone. I also don’t indicate where to strip away whitespace (I did previously, but that took up like half the pseudocode.) So if there’s a place where you suspect whitespace can occur, strip it away and increment the cursor by the length of that whitespace.

new variable: count = 0  // can be either a global variable or given to the function as a reference
                         // keeps track of how many nodes we've seen
new variable: cursor = 0 // also either a global or a reference
                         // keeps track of where in the string we are

tree_builder(newick_string) {
    *** Look for things relating to the left child of this node ***
    if $newick_string at $cursor is '(' {
        * increment the $cursor to account for the open parenthesis
        if newick_string at cursor is '(' {
            *** Then the $left node is an internal node: requires recursion ***
            * recursive call to get node on $left side: this.left = tree_builder(newick_string)
            * doubly link the child and $parent: this.left.parent = this
        }
        * try to find a valid $name next at the current cursor position
        if a name is found {
            *** Then the $left node is a leaf node: parse the leaf data ***
            * create a new $left node
            * provide it with the discovered $name
            * assign $count to left.$serial and increment the $count
            * doubly link it with its left.$parent: this.left.parent = this
            * increment the $cursor up by the $length of the $name
        }
    }
    if $newick_string at $cursor == ':' {
        *** Always expect left branch length after descending into the left child ***
        * increment the $cursor to account for the colon
        * try to find a valid $branch_length_string (which is a floating point value)
        * this.$left.$score = branch_length_string
        * increment the $cursor up by the $length of the $branch_length_string (expressed as a string!)
    }
    *** Look for things related to the right node ***
    if $newick_string at $cursor == ',' {
        * increment the $cursor to account for the comma
        if newick_string at cursor is '(' {
            *** Then the $right node is an internal node: requires recursion ***
            * recursive call to get node on $right side: this.right = tree_builder(newick_string)
            * doubly link the child and $parent: this.rightparent = this
        }
        * try to find a valid $name next at the current cursor position
        if a name is found {
            *** Then the $right node is a leaf node: parse the leaf data ***
            * create a new $right node
            * provide it with the discovered $name
            * assign $count to right.$serial and increment the $count
            * doubly link it with its right.$parent: this.right.parent = this
            * increment the $cursor up by the $length of the $name
        }
    }
    if $newick_string at $cursor == ':' {
        *** Always expect the right branch length after descending into right child ***
        * increment the $cursor to account for the colon
        * try to find a valid $branch_length_string (which is a floating point value)
        * this.$right.$score = branch_length_string
        * increment the $cursor up by the $length of the $branch_length_string (expressed as a string!)
    }
    if $newick_string at $cursor == ')' {
        * increment the $cursor to account for the close parenthesis
    }
    *** Always expect the branch length of this very node after analyzing both its children ***
    if $newick_string at $cursor == ':') {
        * increment the $cursor to account for the colon
        * try to find a valid $branch_length_string (which is a floating point value)
        * this.$score = branch_length_string
        * increment the $cursor up by the $length of the $branch_length_string (expressed as a string!)
    }
    if $newick_string at $cursor == ';') {
        *** This case only executes for the root node-- the very last node to finish parsing ***
        * increment the $cursor to account for the semicolon (optional, keeps it consistent)
        * assign $count to this.$serial (no need to increment $count here)
    }
    *** Return node to complete an instance in recursion (internal) or a base case (leaf) ***
    * return this (not needed if you've been using JavaScript with the "new" operator all along)
}

The implementation that’s included in the attached JavaScript does two things differently than the above. First, I don’t force the user to break encapsulation by declaring globals. Instead, I use an object called “ref” which has two fields, “ref.count” and “ref.cursor”. The name “ref” is chosen to remind us that its fields are passed by reference. This is possible because the object “ref” itself is passed by reference (I could have called it anything, but I chose a name that suited its purpose). Imagine trying to pass “count” and “cursor” in this recursive function without an enclosing object — what would happen instead is that the value wouldn’t be updated, instead the integer values would be copied and modified locally in the span of single function instances. The “ref” object is passed as an argument to the “_tree_builder(<ref>, <newick_string>)” function internally where it is instantiated if “null” is passed in the place of “ref”. The calling user doesn’t even need to know about it, as it’s all wrapped together in a pretty package and the user just calls “tree_builder(<newick_string>)” as before — without the need for globals.

Finally, there is a traversal function, and an expose function. The traversal function returns the node objects in an array following in the natural depth-first post-order described previously. The expose function is a debugging function which writes the output using “thoughts_write(<message>)” which wraps “document.write(<message>)”. You can change “thoughts_write(<message>)” to print output elsewhere using “document.getElementById(<some_identity>).innerHTML += (<message>)” where “some_identity” is the “id” of some element in your HTML. Without going into detail, the traversal function also uses an internal “ref” object which refers to the array as it is filled.

Some other things you can try…

The JavaScript recursive descent parser is actually a simplified version of something that I threw together earlier. The major difference is that I tag leaf nodes with fasta protein sequences by passing a reference to an associative array (or hash) as an argument to “tree_builder(<newick_string>, <fasta_hash>)”. Remember, in JavaScript, an associative array is an instance of an Object, not an instance of an Array. Using non-integer field names in an Array is actually not well defined but kind of sort of works semi-consistently between browsers (i.e. don’t try!), but that’s a story for another day. Whenever the name of a leaf is parsed, I would look it up in the hash and put it in a field either “this.left.fasta” or “this.right.fasta” thereby conferring to the leaf nodes of the in-memory structure the appropriate fasta protein sequence.

Lessons Learned

In putting this thing together, I managed to relearn JS, recursive descent parsing and making JS pass things by reference up and down a recursive stack of function calls. Andre Masella helpfully reminded me that I didn’t need to use any kind of BNF or LALR(1) parser — just an easy single-function parser would do. This is actually a port of a C# parser which does the same thing that I wrote in an earlier step for phylogenetic analysis — the difference being that C# offers a “ref” keyword that allows one to specify arguments in a function’s parameter list as emulated references (functionally equivalent to using C’s asterisk and ampersand convention though not operationally equivalent).

Happy parsing! The code presented should be easy enough to understand for you to port it into the language of your choice for whatever purposes you design.

Brief: The Newick format offers a nice flat representation of a tree. This is done by performing a depth-first (prefix) traversal on the tree and documenting each of the nodes and lengths of edges as they occur during that traversal. Note that this representation is only valid for directed acyclic graphs and inherently preserves the parent-child relationships between the nodes. While there is no restriction on where a root node is for a particular set of data, the format indirectly specifies a root node as the last node to be visited in the traversal. The Newick format is used in phylogenetic trees, and is inherited by MUSCLE through compatibility with PHYLIP. The format does not state a particular arity, although the culture of phylogenetics has made the binary tree the most common flavour. Finally, due to the regular nature of its encoding, Newick format strings are just as regular to convert back to their in-memory representations.