generating random newick tree

Question

[Quak]

What are some smart ways of generating newick tree string randomly, say, with 128 leaf for example ...

Answer 1

[Brice Sarver]

There are several ways to do this in R.

rtree() in the ape library will simulate a random tree.

The TreeSim library will allow you to simulate trees under various parameter combinations and constrain on the number of taxa, age, etc. I use it for simulations and when I need a quick dummy tree.

Save the objects in Newick format once you've got what you want.

[Quak]

thanks; The thing is I would like the tree to be equidistant !! I should have said that earlier in the question, It would be nice to know how can I constrain the simulation to make equidistance tree ...

[Brice Sarver]

Just to be clear, by 'equidistant' do you mean 'ultrametric'? TreeSim will produce ultrametric trees.

[Quak]

sorry about the confusion; I have pasted an image under the other answer ... I hope that makes it clear :-)

Answer 2

[Pierre Lindenbaum]

A quick solution in C?

$ gcc -o a.out -Wall randnewick.c
$ ./a.out 50
((((id6:0.989116,(id41:0.360497)id13:0.950718,id17:0.707824,id35:0.470217)id4:0.527722,((id19:0.181608,id25:0.906145)id15:0.063857)id9:0.211315,(id27:0.806891)id21:0.070135,id39:0.343071)id1:0.669585,(((id23:0.050679)id22:0.536582,id37:0.194032)id3:0.561614,id5:0.709683,id48:0.208214)id2:0.923997,((id38:0.891580)id16:0.737224,(id47:0.927089)id32:0.326778)id7:0.567435,(id31:0.801572,id34:0.805844,id43:0.258143)id11:0.844238)id0:0.012241,((id12:0.920365,id26:0.932368)id10:0.493677,((id45:0.407019,id46:0.991169)id29:0.387065,id42:0.427880)id18:0.064881,(id24:0.585694)id20:0.089364)id8:0.973614,((id33:0.951334)id30:0.562422,id36:0.292341,id40:0.655812)id14:0.842271,id28:0.279305,id44:0.499579)id49;

view raw README.md hosted with ❤ by GitHub

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include <time.h>
	typedef struct Node
	{
	int id;
	double v;
	struct Node* child;
	struct Node* next;
	struct Node* parent;
	}Node,*NodePtr;
	static void insert(NodePtr root,NodePtr n)
	{
	int choice=(rand()%2);
	if(choice==0 && root->parent!=NULL)
	{
	if(root->next==NULL)
	{
	n->parent=root->parent;
	root->next=n;
	}
	else
	{
	insert(root->next,n);
	}
	}
	else
	{
	if(root->child==NULL)
	{
	n->parent=root;
	root->child=n;
	}
	else
	{
	insert(root->child,n);
	}
	}
	}
	static void printTree(NodePtr root)
	{
	NodePtr n;
	if(root->child!=NULL)
	{
	printf("(");
	for(n=root->child;n!=NULL;n=n->next)
	{
	if(n!=root->child) printf(",");
	printTree(n);
	}
	printf(")");
	}
	printf("id%d",root->id);
	if(root->parent!=NULL) printf(":%f",root->v);
	}
	int main(int argc,char** argv)
	{
	int i,n=atoi(argv[1])-1;
	Node root;
	memset((void*)&root,0,sizeof(Node));
	srand(time(NULL));
	for(i=0;i<n;++i)
	{
	NodePtr node=(NodePtr)malloc(sizeof(Node));
	memset((void*)node,0,sizeof(Node));
	node->v = (double)rand()/(double)RAND_MAX;
	node->id=i;
	insert(&root,node);
	}
	root.v = (double)rand()/(double)RAND_MAX;
	root.id=i;
	printTree(&root);
	printf(";\n");
	return 0;
	}

view raw randnewick.c hosted with ❤ by GitHub

[Quak]

Great; I am trying to tweak it; basically, I would like to have a equidistance tree ... something like this, with 128 or more leafs ...

[Pierre Lindenbaum]

Easy if you only specify the number of terminal nodes. Is it what you want?

[Quak]

Exactly;

Given 7 number of nodes, ./a.out 7 It returns

(((id5:1.000000)id3:1.000000)id0:1.000000,(id2:1.000000)id1:1.000000,id4:1.000000)id6;

which does not look as I expect either.

[Pierre Lindenbaum]

In your example, there are 3 terminal nodes, not 7.

[Quak]

Yes, 7 is the total number of nodes; meaning 4 leafs, 2 parents and 1(origin).