Converting Taxonomic Lineages Into A Common Tree

Question

[Pawel Szczesny]

I have a number of lineages like this:

Bacteria;Chlamydiae;Chlamydiae;Chlamydiales;Chlamydiaceae;Chlamydophila;
Bacteria;Firmicutes;Bacilli;Lactobacillales;Lactobacillaceae;Lactobacillus;
Bacteria;Firmicutes;Bacilli;Lactobacillales;Streptococcaceae;Streptococcus;
... (the list continues)

Is there any tool capable of converting these lineages into common tree in Nexus or Newick format?

[jhc]

You may also want to take a look at this: http://www.biostars.org/post/show/13452/parsing-ncbi-taxonomic-tree/#13464

Answer 1

[Pierre Lindenbaum]

The following java program should work:

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Map;
	import java.util.TreeMap;
	import java.util.regex.Pattern;
	public class Biostar52895
	{
	private static class Node
	{
	Map<String,Node> children=new TreeMap<String, Biostar52895.Node>();
	void fill(String tokens[],int index)
	{
	Node c=children.get(tokens[index]);
	if(c==null)
	{
	c=new Node();
	this.children.put(tokens[index],c);
	}
	if(index+1< tokens.length) c.fill(tokens, index+1);
	}
	void printChildren()
	{
	boolean first=true;
	System.out.print("(");
	for(String childName:this.children.keySet())
	{
	if(!first) System.out.print(",");
	first=false;
	Node c=this.children.get(childName);
	c.print(childName);
	}
	System.out.print(")");
	}
	void print(String myName)
	{
	if(!this.children.isEmpty())
	{
	printChildren();
	}
	System.out.print(myName);
	}
	}
	private Node root=new Node();
	private void parse(BufferedReader in) throws IOException
	{
	Pattern semicolon=Pattern.compile("[;]");
	String line;
	while((line=in.readLine())!=null)
	{
	if(line.isEmpty()) continue;
	String tokens[]=semicolon.split(line);
	root.fill(tokens, 0);
	}
	}
	private void print()
	{
	this.root.printChildren();
	System.out.println(";");
	}
	public static void main(String[] args) throws IOException
	{
	Biostar52895 app=new Biostar52895();
	app.parse(new BufferedReader(new InputStreamReader(System.in)));
	app.print();
	}
	}

view raw Biostar52895.java hosted with ❤ by GitHub

compile & run:

javac Biostar52895.java

$ echo "Bacteria;Chlamydiae;Chlamydiae;Chlamydiales;Chlamydiaceae;Chlamydophila;
Bacteria;Firmicutes;Bacilli;Lactobacillales;Lactobacillaceae;Lactobacillus;
Bacteria;Firmicutes;Bacilli;Lactobacillales;Streptococcaceae;Streptococcus;" | java Biostar52895

((((((Chlamydophila)Chlamydiaceae)Chlamydiales)Chlamydiae)Chlamydiae,((((Lactobacillus)Lactobacillaceae,(Streptococcus)Streptococcaceae)Lactobacillales)Bacilli)Firmicutes)Bacteria);

[Pawel Szczesny]

Biostars classic :) "Is there a tool that ...?" Pierre's answer: "Yes, there is. Let me write it for you." Thank you very, very much Pierre.

[david]

hey pierre. thanks a lot for this solution. probably a stupid question but i'm a biochemist and this is my first java program ever. i've compiled your program on my mac os x 10.8 and want to run it now, but it just goes into an endless loop. how is the input (the list) specified. thx!

[bioinfo]

@Pierre, I tried the javascript but somehow it didn't work. Did my miss some dependencies of java packages or something in my installed java program? ( I have no knowledge in java)

echo "Bacteria;Chlamydiae;Chlamydiae;Chlamydiales;Chlamydiaceae;Chlamydophila;Bacteria;Firmicutes;Bacilli;Lactobacillales;Lactobacillaceae;Lactobacillus;Bacteria;Firmicutes;Bacilli;Lactobacillales;Streptococcaceae;Streptococcus;" | java Biostar52895

error message:

Exception in thread "main" java.lang.NoClassDefFoundError: Biostar52895
Caused by: java.lang.ClassNotFoundException: Biostar52895
        at java.net.URLClassLoader$1.run(URLClassLoader.java:217)
        at java.security.AccessController.doPrivileged(Native Method)
        at java.net.URLClassLoader.findClass(URLClassLoader.java:205)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:323)
        at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:294)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:268)
Could not find the main class: Biostar52895. Program will exit.

[Pierre Lindenbaum]

it's not javascript, it's java. It's compiled compiled with javac Biostar52895.java and executed with java Biostar52895

[bioinfo]

Now I see javac didn't compile the Biostart52895.java and the expected .class file was missing. can you point me why?

javac Biostar52895.java
Output:
Biostar52895.java:13: > expected
        Map<String,Node> children=new TreeMap<String, Biostar52895.Node="">();
                                                                       ^
Biostar52895.java:13: ';' expected
        Map<String,Node> children=new TreeMap<String, Biostar52895.Node="">();
                                                                        ^
Biostar52895.java:13: illegal start of type
        Map<String,Node> children=new TreeMap<String, Biostar52895.Node="">();
                                                                          ^
Biostar52895.java:13: <identifier> expected
        Map<String,Node> children=new TreeMap<String, Biostar52895.Node="">();
                                                                           ^
Biostar52895.java:13: ';' expected
        Map<String,Node> children=new TreeMap<String, Biostar52895.Node="">();
                                                                            ^
Biostar52895.java:70: '(' or '[' expected
        app.parse(new BufferedReader(new InputStreamReaderSystem.in)));
                                                                   ^
Biostar52895.java:70: ';' expected
        app.parse(new BufferedReader(new InputStreamReaderSystem.in)));
                                                                     ^
7 errors

[Pierre Lindenbaum]

Ah, I see, it's because the code has been changed by the new version of biostars. It thinks it's HTML.

Give me a few minutes....

[Pierre Lindenbaum]

It's now uploaded on github:

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Map;
	import java.util.TreeMap;
	import java.util.regex.Pattern;
	public class Biostar52895
	{
	private static class Node
	{
	Map<String,Node> children=new TreeMap<String, Biostar52895.Node>();
	void fill(String tokens[],int index)
	{
	Node c=children.get(tokens[index]);
	if(c==null)
	{
	c=new Node();
	this.children.put(tokens[index],c);
	}
	if(index+1< tokens.length) c.fill(tokens, index+1);
	}
	void printChildren()
	{
	boolean first=true;
	System.out.print("(");
	for(String childName:this.children.keySet())
	{
	if(!first) System.out.print(",");
	first=false;
	Node c=this.children.get(childName);
	c.print(childName);
	}
	System.out.print(")");
	}
	void print(String myName)
	{
	if(!this.children.isEmpty())
	{
	printChildren();
	}
	System.out.print(myName);
	}
	}
	private Node root=new Node();
	private void parse(BufferedReader in) throws IOException
	{
	Pattern semicolon=Pattern.compile("[;]");
	String line;
	while((line=in.readLine())!=null)
	{
	if(line.isEmpty()) continue;
	String tokens[]=semicolon.split(line);
	root.fill(tokens, 0);
	}
	}
	private void print()
	{
	this.root.printChildren();
	System.out.println(";");
	}
	public static void main(String[] args) throws IOException
	{
	Biostar52895 app=new Biostar52895();
	app.parse(new BufferedReader(new InputStreamReader(System.in)));
	app.print();
	}
	}

view raw Biostar52895.java hosted with ❤ by GitHub

[bioinfo]

Thanks Pierre. It's working now..!! Excellent.