3
$\begingroup$

I am working on large scale biodiversity simulations and have collected a lot of data on simulated phylogenies. I have a list of child-parent edgelist species in the form:

list = [1, 1, 2, 2]

      /-- 3
1 -- 2
      \-- 4 

children = [1, 2, 3, 4]
parents = [1, 1, 2, 2]   

Where the index is the child and the value is the parent. 1 is it's own parent (the root).

I have such a tree for a large dataset upwards of 1000 individuals. I can build the tree programmatically in igraph or networkx easily and visualise it. However, I cannot find a way to convert the tree into a format for phylogenetic analysis. There are function to convert dendropy and ete trees from igraph/networkx into their own formats but no way to re-import the igraph/networkx trees. There also appear to be no way to write the igraph/networkx trees into phylo formats (newick).

There also seems to be no support in dendropy or ete to programmatically build trees and it would be infeasible to manually build all the trees I have.

Is there a way to build the trees so I can analyse and visualise them as phylogenies?

Tried approach

library(ape)
p <- c(NA, 1, 1, 3, 3, 4, 4)
x<-data.frame(name=as.character(c(1:7)) , id=1:7,  parent = c(NA, 1,   1, 3, 3, 4, 4))
x1<-na.omit(x)[,3:2]
n <- c(c(1, 3, 4), c(2, 5, 6, 7))
edges <- matrix(c( x1$parent, x1$id), ncol=2)

tree<-list(edge=edges, Nnode = 3, tip.label = as.character(x$name[c(2, 5, 6, 7)]), node.label = as.character(x$name[c(1, 3, 4)]))

class(tree)<-"phylo"

#plot.phylo(tree, show.node.label=TRUE)

The plot command just causes R to crash and the tree object has an invalid structure.

$\endgroup$
  • $\begingroup$ Perhaps stat.ethz.ch/pipermail/r-sig-phylo/2009-July/000405.html, let me know if this works. I'm not very skilled in R myself, unfortunately! (just for converting edge list matrix to phylo) $\endgroup$ – CKM Aug 21 '15 at 22:55
  • $\begingroup$ Thanks. I tried to get this code to work but I keep on getting errors with my edgelist. I also found this question on stack overflow convert df to dendrogram. However I don't think their code would work for an edge-list as it seems to require all possible paths to mapped into a dataframe. I will add an example of what I tried to the question. $\endgroup$ – Sanalphatau Aug 22 '15 at 12:46
  • $\begingroup$ It seems like standard edge list format is two columns (e.g., for igraph: shizukalab.com/toolkits/sna/sna_data). Can you output your list in that format? $\endgroup$ – kmm Aug 22 '15 at 13:42
  • $\begingroup$ sure ill edit the first example. In the second example the child list is [1:7]. I believe the graph should be possible using graph.adjlist(mylist, mode = 'out') $\endgroup$ – Sanalphatau Aug 22 '15 at 14:44
  • $\begingroup$ It looks like the phylo constructor changed since the link posted above: stat.ethz.ch/pipermail/r-sig-phylo/2014-May/003467.html $\endgroup$ – kmm Aug 22 '15 at 15:24
3
$\begingroup$

This will be a complete answer, but it's got code, so it won't work as a comment. Working backwards from rtree(3), here's a way to build a phylo object from component parts, which might be helpful:

children <- c(5, 1, 2, 3)
parents <- c(4, 5, 5, 4)
x <- matrix(c(parents, children), ncol = 2)
tr <- list(edge = x, tip.label = 1:3, Nnode = 2)
class(tr) <- "phylo"
plot(tr)

Doing the same with your children and parents, doesn't work, however.

children <- c(1, 2, 3, 4)
parents <- c(1, 1, 2, 2)
x <- matrix(c(parents, children), ncol = 2)
tr <- list(edge = x, tip.label = 1:3, Nnode = 2)
class(tr) <- "phylo"
tr

Gives

Error in if (tabulate(phy$edge[, 1])[length(phy$tip.label) + 1] > 2) FALSE else TRUE : missing value where TRUE/FALSE needed

I don't know hot to make the edge list conform to the expected order for a phylo.

$\endgroup$
  • $\begingroup$ yeah I get the same problem. Maybe R isn't the answer. I really only want to extract the newick tree so I can analyse the tree probably in python. $\endgroup$ – Sanalphatau Aug 23 '15 at 13:50
2
$\begingroup$

@kmm's code works with a few tweaks. One problem your edgelist has is that it contains a singleton node, which ape does not like to deal with. Turning it into a proper phylo object means removing the singleton 'root' node and instead making the child of this singleton node the root. Here is an example using a slightly larger tree, which demonstrates how to make a tree with both leaf nodes and internal, non-root nodes.

The trickiest part is translating the parents and children list into ape's unusual internal numbering system.

phylo_from_el <- function(el){
  i <- 0
  for(n in el[2:length(el)]){
    i <- i+1
    parents[i] <- n 
    children[i] <- i+1
  }
  nnode <- sum(children %in% parents) + 1
  nleaf <- length(el)-nnode
  # Translate preorder sequence into ape sequence
  ttable <- matrix(c(1:length(el), rep(0, length(el))), ncol=2)
  ttable[unique(parents),2] <- 1:nnode + nleaf
  ttable[-unique(parents),2] <- 1:nleaf

  parents_t <- sapply(parents, FUN = function(x)ttable[x,2])
  children_t <- sapply(children, FUN = function(x)ttable[x,2])

  edge <- matrix(c(parents_t, children_t), ncol = 2)
  tr <- list(edge = edge, tip.label = 1:nleaf, Nnode = nnode)
  class(tr) <- "phylo"
  return(tr)
}
el <- c(1,1,1,3,3)

tr <- phylo_from_el(el)

plot(tr)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.