Convert From Newick To Dot Language

Question

[ajingnk]

I want to plot tree like human kinome. Looks like only GraphViz can do that with Spring-Electrical Model for graph generation. A life of tree are shown here made by GraphViz.

However, my tree is in Newick format. Is there any easy way to convert Newick format to DOT language?

Thanks!

[Pierre Lindenbaum]

googled and found: http://jean-paul.davalan.pagesperso-orange.fr/graphs/ph/index-en.html

[ajingnk]

That is not quit right. For example, you can try to paste: "((D:10,C:4)D_C,B:4,A:13)" as input. However, the result doesn't match the input. Probably, it only works for very specific Newick format.

Answer 1

[Pierre Lindenbaum]

OK, I've changed the code of one my my previous answer "newick to json:" http://plindenbaum.blogspot.fr/2012/07/parsing-newick-format-in-c-using-flex.html

Here is the code:

	all:
	bison -d newick.y
	flex newick.l
	gcc -Wall -O3 newick.tab.c lex.yy.c
	echo "((D:10,C:4)D_C,B:4,A:13);" | ./a.out

view raw Makefile hosted with ❤ by GitHub

	%{
	#include "newick.tab.h"
	static size_t string_length=0;
	void* saferealloc(void *ptr, size_t size)
	{
	char* p= realloc(ptr,sizeof(char)*(size));
	if(p==NULL)
	{
	fprintf(stderr,"out of memory");
	exit(EXIT_FAILURE);
	}
	return p;
	}
	static char* copy(const char* s,size_t length)
	{
	char* p= saferealloc(NULL,sizeof(char)*(length+1));
	strncpy(p,s,length);
	p[length]=0;
	return p;
	}
	static char* append(size_t* len,const char* s2,size_t len2)
	{
	yylval.s= saferealloc( yylval.s,sizeof(char)*(*len+len2+1));
	strncpy(&yylval.s[*len],s2,len2);
	yylval.s[*len+len2]=0;
	*len+=len2;
	return yylval.s;
	}
	%}
	%s apos
	%s quot
	%%
	<quot>{
	\\" append(&string_length,"\"",1);
	\' append(&string_length,"\'",1);
	\" {BEGIN(INITIAL);return STRING;}
	}
	<apos>{
	\\' append(&string_length,"\'",1);
	\" append(&string_length,"\"",1);
	\' {BEGIN(INITIAL);return STRING;}
	}
	<apos,quot>{
	\n append(&string_length,"\n",1);
	\t append(&string_length,"\t",1);
	\\ append(&string_length,"\",1);
	([^\"\'\]|\n)+ append(&string_length,yytext,yyleng);
	}
	\: return COLON;
	\; return SEMICOLON;
	\) return CPAR;
	\( return OPAR;
	\, return COMMA;
	\" {string_length=0;BEGIN(quot); }
	\' {string_length=0;BEGIN(apos); }
	[a-zA-Z_][a-zA-Z_0-9]* {yylval.s=copy(yytext,yyleng); return STRING;}
	[\+|\-]?[0-9]+ {yylval.d=copy(yytext,yyleng); return NUMBER;}
	[\+|\-]?[0-9]+\.[0-9]+([e|E][0-9]+)? {yylval.d=copy(yytext,yyleng); return NUMBER;}
	[ \t\n\r] ;
	. {fprintf(stderr,"Syntax error (%c)\n",yytext[0]);exit(EXIT_FAILURE);}
	%%

view raw newick.l hosted with ❤ by GitHub

	%{
	#include <stdio.h>
	#include <stdlib.h>
	#include <errno.h>
	#include <string.h>
	extern int yylex();
	extern FILE* yyin;
	extern void* saferealloc(void *ptr, size_t size);
	int yywrap() { return 1;}
	void yyerror(const char* s) {fprintf(stderr,"Error:\"%s\".\n",s);}
	struct tree_t
	{
	int id;
	char* label;
	char* length;
	struct tree_t* child;
	struct tree_t* next;
	};
	typedef struct tree_t Tree;
	static int id_generator=0;
	static Tree* newTree()
	{
	Tree* t=saferealloc(0,sizeof(Tree));
	memset(t,0,sizeof(Tree));
	t->id=(++id_generator);
	return t;
	}
	static void freeTree(Tree* t)
	{
	if(t==NULL) return;
	free(t->label);
	free(t->length);
	freeTree(t->child);
	freeTree(t->next);
	free(t);
	}
	static void escape(FILE* out,const char* s)
	{
	if(s==NULL) { fputs("null",out); return;}
	while(*s!=0)
	{
	switch(*s)
	{
	case '\'': fputs("\\'",out); break;
	case '\"': fputs("\\"",out); break;
	case '\': fputs("\\",out); break;
	case '\n': fputs("\n",out); break;
	case '\r': fputs("\r",out); break;
	case '\t': fputs("\t",out); break;
	default : fputc(*s,out); break;
	}
	++s;
	}
	}
	static void num(FILE* out,const char* d)
	{
	if(d==NULL) { fputs("null",out);; return;}
	fputs(d,out);
	}
	static void printTree(FILE* out,const Tree* t)
	{
	fprintf(out,"id%d[label=\"",t->id);
	if(t->label!=NULL) escape(out,t->label);
	if(t->length!=NULL) {if(t->label!=NULL) fputc(':',out);escape(out,t->length);}
	fputs("\"];\n",out);
	if(t->child!=0)
	{
	const Tree* c=t->child;
	while(c!=NULL)
	{
	printTree(out,c);
	fprintf(out,"id%d -> id%d\n",t->id,c->id);
	c=c->next;
	}
	}
	}
	%}
	%union {
	char* s;
	char* d;
	struct tree_t* tree;
	}
	%error-verbose
	%token OPAR
	%token CPAR
	%token COMMA
	%token COLON SEMICOLON
	%token<s> STRING
	%token<d> NUMBER
	%type<s> label optional_label
	%type<d> number optional_length
	%type<tree> subtree descendant_list_item descendant_list
	%start input
	%%
	input: descendant_list optional_label optional_length SEMICOLON
	{
	Tree* tree=newTree();
	//tree->type=ROOT;
	tree->child=$1;
	tree->label=$2;
	tree->length=$3;
	fputs("digraph G {\n",stdout);
	printTree(stdout,tree);
	freeTree(tree);
	fputs("}\n",stdout);
	};
	descendant_list: OPAR descendant_list_item CPAR
	{
	$$=$2;
	};
	descendant_list_item: subtree
	{
	$$=$1;
	}
	|descendant_list_item COMMA subtree
	{
	Tree* last=$1;
	$$=$1;
	while(last->next!=NULL)
	{
	last=last->next;
	}
	last->next=$3;
	}
	;
	subtree : descendant_list optional_label optional_length
	{
	$$=newTree();
	$$->child=$1;
	$$->label=$2;
	$$->length=$3;
	}
	| label optional_length
	{
	$$=newTree();
	$$->label=$1;
	$$->length=$2;
	}
	;
	optional_label: { $$=NULL;} | label { $$=$1;};
	optional_length: { $$=NULL;} | COLON number { $$=$2;};
	label: STRING { $$=$1;};
	number: NUMBER { $$=$1;};
	%%
	int main(int argc,char** argv)
	{
	yyin=stdin;
	yyparse();
	return EXIT_SUCCESS;
	}

view raw newick.y hosted with ❤ by GitHub

	digraph G {
	id6[label=""];
	id3[label="D_C"];
	id1[label="D:10"];
	id3 -> id1
	id2[label="C:4"];
	id3 -> id2
	id6 -> id3
	id4[label="B:4"];
	id6 -> id4
	id5[label="A:13"];
	id6 -> id5
	}

view raw output.dot hosted with ❤ by GitHub

input:

echo "((D:10,C:4)D_C,B:4,A:13);" | ./a.out

output:

digraph G {
id6[label=""];
id3[label="D_C"];
id1[label="D:10"];
id3 ->  id1
id2[label="C:4"];
id3 ->  id2
id6 ->  id3
id4[label="B:4"];
id6 ->  id4
id5[label="A:13"];
id6 ->  id5
}

[ajingnk]

For D:10, 10 is the weight of edge between D and D_C. Anyway to adapt the weight as proportional length of edge into the dot language?

[Pierre Lindenbaum]

yep, I know, but I'm lazy :-) have a look at the 'edge attributes http://www.graphviz.org/doc/info/attrs.html#d:weight and change the 'while' loop in the newick.y file.