Unifying Phylogenetics

[TransGirlCodes]

With the addition of the PhyloTrees.jl and PhyloNetworks.jl packages to the julia ecosystem (#230), it is clear that the types ad methods provided by Phylo need yet another re-work.

Whilst the current design of types in Phylo make the use of graph data structures in LightGraphs.jl, this makes them really very different from types in PhyloTrees and PhyloNetworks, meaning the types and methods in Bio.Phylo do not constitute a useful infrastructure for these other phylogenetics researchers and coders, who have developed their own phylogenetic data types.

The data types in these packages share commonalities in structure, which makes it possible to take the parametric metadata ideas in Bio.Phylo to create a common phylogenetic tree/network type useable by the authors of these packages and others for their packages and work.

Design and code drafts to follow.
Development will occur on unify_phylo branch.

[cecileane]

Just a few scattered thoughts.

There might an advantage to try and use a data type that can easily be converted into the "phylo" class in the R package ape: the core for many specialized R packages for phylogenetic comparative methods of all kinds (see this taks view.
RCall.jl makes it very easy to call R within Julia, at least if data types are simple (like matrices). I am really all for native Julia code, but for now users have a lot of phylogenetics tools in R. A data structure that is easy to export to R could facilitate a smooth transition of R users towards Julia.

The "phylo" class in ape is basically a list:

• edge: matrix of integers, one row per edge, 2 columns: one for the index of the parent node, one for the child node
• Nnode: integer, number of internal nodes
• tip.label: vector of strings for the tip labels
• edge.length (optional): numeric vector
• nodel.label (optional): label of internal nodes
• root.edge (optional): edge length

An often implicit assumption of functions in ape and related packages, is that nodes 1 through n are the n tips, and node n+1 is the root.

The data type in PhyloNetworks.jl is completely different: nodes link to their edges and edges link to their nodes to allow for fast tree traversals. It also allows for an easy manipulation of trees when searching for the best topology: to perturb the tree locally (NNI moves, removal/addition of a hybrid edge etc).

It looks like the data structure in PhyloTrees.jl has matrices like in ape, but not a single edge matrix: so there is some redundant information because each node knows the index of its edges, and each edge knows the index of its nodes, which should ease tree traversals.

[TransGirlCodes]

I'm a regular user of ape myself - mutation counting code and distance code I've just completed is based very much on its C code :). I'm all for interoperating with ape. In the current Bio.Phylo type, the similar assumptions to ape are made regarding the numbering of the nodes. The new type will do as both PhyloNetworks and PhyloTrees do and have edges and node types, rather than use the LightGraphs. But conversion to the matrix format should definitely be possible!

[jangevaare]

A bit of a summary of the PhyloTrees data structures...

In PhyloTrees.jl, a tree is a vector of node objects, and a vector of edge objects. The indices of nodes and edges in these vectors serve as the node and edge IDs. Each node knows of it's branches, and each branch knows of it's nodes. Branch length in the branch type is a Nullable{Float64}. Pretty barebones. I can include the code (save the constructors) below easily.

I'm unsure if the redundancy in this data structure is worthwhile or not. I haven't run any comparisons. It certainly made writing code easier for me though.

type Node
  in::Vector{Int64}
  out::Vector{Int64}
end

type Branch
  source::Int64
  target::Int64
  length::Nullable{Float64}
end

type Tree
  nodes::Vector{Node}
  branches::Vector{Branch}
end

[TransGirlCodes]

@cecileane Furthur to your suggestion of ape interoperability, I've just been reading Rcall.jl and it looks like it should be trivial to get the ape phylogenetic tree structures from R as we could just process the Rcall.RObject variable that is returned from the rcall / reval functions. Putting trees into R from julia might be a bit more complex, I haven't read so far ahead yet, but if I can't glean from the docs how that might be done I'll ask the authors.

[mkborregaard]

Just to add a few cents of mine, I came to julia after developing a phylogeny-using package in R, and found @Ward9250 's Phylo types. After getting used to the graph-like implementation I found it MUCH easier to program with than the ape format. For instance, ape uses several different sorting orders of nodes because some sorting orders are more efficient for some processes. The sorting order has to be guessed from the position of nodes in the edge matrix. Many internal ape functions rely on shifting sorting order (ape-package.ird.fr/misc/FormatTreeR_24Oct2012.pdf). In @Ward9250 's code you just use a different iterator, e.g. a DepthFirst, when that is most appropriate.

I have heard many express chagrin over the issues caused in R over having that legacy format. I wrote some code a year ago for plotting phylogenies to compose contexts (see https://drive.google.com/file/d/0BwWjA0Ez4iLhRTVVTEpqTXJiTXc/view?usp=sharing , scroll down for plots), and comparing that relatively clean and legible code to the ape::plot.phylo code is instructive. I would thus advise against basing julia code on this format.

That said, it'd be very easy to calculate ape-trees from the Phylo format, and put it into an R session, something like (untested code, as this is based on my old version of @Ward9250 s branch ):

using RCall, Bio.Phylo

# calculate numerics
ids = Dict(PhyNode, Int)
tips = 0
nodes = 0
ntips = terminaldescendents(phy)
totalnodes = length(DepthFirst(phy))
Nnode = ntips - totalnodes

# get the tip.label vector
tiplabel = [node.name for node in DepthFirst(phy) if isleaf(node)]

# assign ape ids to nodes and leafs
for clade in DepthFirst(phy)
    ids[clade] = isleaf(clade) ? tips += 1 : ntips + nodes += 1
end

# build the edge matrix
edge = Matrix{Int}(totalnodes - 1, 2)
for (i, clade) in enumerate(DepthFirst(phy)[2:end])
    edge[i, 1] = ids[parent(clade)]
    edge[i, 2] = ids[clade]
end

# edgelengths and such are easy to add

R"""
library(ape)
phy = list(Nnode = $Nnode, edge = $edge, tip.label = $tiplabel)
class(phy) = "phylo"
plot(phy)
"""

[TransGirlCodes]

@mkborregaard For the benefit of everyone, since you have an old branch could you please copy-paste the old definition of phylogenies and nodes here as @jangevaare did above with PhyloTrees?

[mkborregaard]

Sure. Here they are with documentation and constructors - I can remove that for clarity if desired.

"""
Phylogeny represents a phylogenetic tree.

A tree can have:

- `name`
- `root`
- `rooted`
- `rerootable`
"""
type Phylogeny
    name::String
    root::PhyNode
    rooted::Bool
    rerootable::Bool

    Phylogeny() = new("", PhyNode(), false, true)
end


# Phylogeny Node Type
# --------------------

"""
PhyNode represents a node in a phylogenetic tree.

A node can have:

- `name`
- `branchlength`
- a reference to its `parent` PhyNode
- reference to one or more `children`
"""
type PhyNode
    name::String
    branchlength::Nullable{Float64}
    confidence::Nullable{Float64}
    children::Vector{PhyNode}
    parent::PhyNode
    """
    Create a PhyNode.
    PhyNodes represent nodes in a phylogenetic tree. All arguments are optional
    when creating PhyNodes:

    **Example:**
    one = PhyNode()
    two = PhyNode(name = "two", branchlength = 1.0, parent = one)

    **Parameters:**
    * `name`:         The name of the node (optional). Defaults to an empty string, indicating
                      the node has no name.

    * `branchlength`: The branch length of the node from its parent (optional).
                      Because branch lengths can be not applicable (cladograms), or not known.
                      The value is Nullable, and is null by default.

    * `confidence`:   A Nullable Floating point value that can represent confidence for that clade (optional).
                      Such confidences are usually Maximum Likelihood values or Bootstrap
                      values.

    * `children`:     A Vector containing references to the PhyNodes that are children of this node (optional).
                      Default to an empty vector.

    * `parent`:       The parent node (optional). Defaults to a self-reference, indicating
                      the node has no parent.
"""
    function PhyNode(name::String = "",
                     branchlength::Nullable{Float64} = Nullable{Float64}(),
                     confidence::Nullable{Float64} = Nullable{Float64}(),
                     children::Vector{PhyNode} = PhyNode[],
                     parent = nothing)
        x = new()
        name!(x, name)
        branchlength!(x, branchlength)
        confidence!(x, confidence)
        if parent != nothing
            graft!(parent, x)
        else
            x.parent = x
        end
        x.children = PhyNode[]
        for child in children
            graft!(x, child)
        end
        return x
    end
end

[mkborregaard]

But I am sure the current implementation based on LightGraphs is better - I have just not started using it yet, and the code I suggested for transferring to R is just back-of-the-envelope.

[TransGirlCodes]

I understand it's back of envelope, but I thought it was nessecary to help everyone understand how things were before I made the LightGraphs implementation of phylogenies. And whilst I made that implementation for what I felt were some solid reasons, if it's so dissimilar to what people using julia for phylogenetics want to do (such as PhyloNetworks and PhyloTrees) that it's not useful, then it fails in its primary objective, no matter my reasons for forcing the switch to LightGraphs on people. So going back towards a linked data structure - which it originally was, and the other two packages use - may well be better, I've already hit on some limitations to the LightGraphs implementation similar to the ape format with regards to node ordering and so on, and I've been dreading addressing them.

[mkborregaard]

I opened an issue at RCall that might be relevant to this: JuliaInterop/RCall.jl#138