The difference between the RF and the NNI distances

Just to complement my answer to a blog post, where I maintain that the Nearest-Neighbor Interchange (NNI) distance is not equivalent to the Robinson-Foulds (RF) distance, a simple example:

Where we can see that trees T1 and T2 differ only in the location of nodes A and B -- on these trees, we can naturally think of the nodes A, B, 1,..., 6 as representing leaves, but they might also be large subtrees.

The RF distance is the number of edges (=branches) that are unique to each tree (that's why it's also called the symmetric difference), and it may be normalized to one. If we highlight the unique edges on trees T1 and T2

We see that the (unnormalized) RF distance is 10. For dichotomic trees, the number of unique edges is the same on both trees.

The NNI distance is the minimum number of NNIs that must be applied to one tree such that it becomes equal to the other. One NNI branch swap will change exactly one edge, thus is very tempting to assume that the NNI distance can be found by looking at the distinct edges.

But the problem is when the same branch is involved in more than one path of the "NNI walk". The RF distance (divided by two, for fully resolved trees) is then a lower bound on the minimum number of NNIs. In our example:

The NNI distance between T1 and T2 is 6, one more than the RF distance since the edge splitting (1,2,3) and (4,5,6) is used twice in the NNI computation. The problem, as explained by Liam, is that simulating trees with a specified distance is hard, and the solution of using very large trees masks the cases where the distances disagree...

Reference:
Bryant D. (2004). The Splits in the Neighborhood of a Tree, Annals of Combinatorics, 8 (1) 1-11. DOI: 10.1007/s00026-004-0200-z

Talk at UVigo: Fine-grain parallelism of MrBayes on multi- and many-core architectures, by Frederico Pratas

Announcement I received about an invited talk at my building, since my group is part of the Galician Network of High Performance Computing (R-GHPC2). I guess the talk will be given in english -- at our meetings we usually find a common ground between english, spanish, galician and portuguese.

Thursday, June 30th of 2011, 12:00 PM
Room 3, Wing B, ground floor of the Experimental Sciences building, University of Vigo

Fine-grain parallelism of MrBayes on multi- and many-core architectures
Frederico Pratas, from the Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento (INESC-ID), Lisboa, Portugal

Currently, we are facing a situation where applications exhibit increasing computational demands. In particular, we observe a considerable increase of complexity in algorithms due to both the increasing amounts of data available for analysis (e.g., genomic databases) and the need for more accurate and precise results (e.g., more complex particle interaction models). In this talk we address how MrBayes, a bioinformatics application that performs Bayesian inference of phylogenetic trees, can benefit from modern multi- and many-core computing architectures. We focus on exploiting fine-grain parallelism by distributing the evaluation of the conditional likelihoods (cl). Namely, we use different types of architectures: General-purpose Processors, Graphics Processing Units (GPU) and Cell Broadband Engine (Cell/BE). Besides, reconfigurable hardware can also be used as a very efficient co-processing solution to accelerate this type of applications. Therefore, we also consider the design steps and implementation of MrBayes on Field Programable Gate Arrays (FPGAs). Overall the results show that, although we can efficiently accelerate the computation of cl on GPUs and FPGAs due to their characteristics, there are still important constraints related with the access to the data in the main memory, which incurs in huge overheads. The general-purpose processors show the best results in terms of speedup.

This talk is supported by the Galician Network of high Performance Computing.
PS: In a previous communication, the address was "Room S4, Wing C, 2º floor" but there should be no problem since they are very near.

some links from iEvoBio - the poor guy's bookmarking

OK, let me just note down these interesting links discussed at iEvoBio - I'm not there but the tubes are - while I prepare for SMBE next week.

• http://leptree.net/
• http://www.evoio.org/
• http://www.nexml.org/
• https://www.nescent.org/wg/evoinfo/index.php?title=PhyloWS
• http://www.evolutionaryontology.org/
• http://www.eol.org/
• http://lifewatch.eu/
• http://www.cate-project.org/
• http://scratchpads.eu/
• http://kiwi.cs.dal.ca/GenGIS/Main_Page
• http://prefuse.org/doc/api/prefuse/data/Tree.html
• http://www.cs.nmsu.edu/~cdaostore/
• http://markov.uoregon.edu/software/phyesta/
• http://gmod.org/wiki/Main_Page
• http://www.obofoundry.org/cgi-bin/detail.cgi
• http://www.ibarcode.org/nextgen
• http://www.dnabank-network.org/
• http://www.dataconservancy.org/
• http://phylotouch.jsphylosvg.com/
• http://code.google.com/p/phylobox/ and http://phylobox.appspot.com/
• http://exon.niaid.nih.gov/nexplorer/
• http://synthesis.eol.org/news/eol-treemap-viewer and http://kurie.github.com/EOL-tree-viewer/#COL
• https://www.phenoscape.org/wiki/Phenex
  

via @rdmpage and @phylogenomics (this blogpost will be updated a few times...)

High Performance Computing conferences in Galicia - May 2010

Next week there will be two meetings here in Galicia on HPC (that I am aware of, at least). The first is Tuesday, on Santiago the Compostela:

Título: Open Cirrus Cloud Computing Testbed
Ponente: Dejan Miljicic, Senior Researcher at HP and Managing Director OPEN CIRRUS
Data: 18 de Maio do 2010
Hora: 11:30h.
Lugar: Sala de Presentaciones do CESGA (Avda. de Vigo s/n)

ABSTRACT:
There are a number of important and useful testbeds, such as PlanetLab, EmuLab, IBM/Google cluster, and Amazon EC2/S3, that enable researchers to study different aspects of distributed computing. However, no single testbed supports research spanning systems, applications, services, open-source development, and datacenters. Towards this end, we have developed Open Cirrus, a cloud computing testbed for the research community that federates heterogeneous distributed data centers. Open Cirrus offers a cloud stack consisting of physical and virtual machines, and global services, such as sign-on, monitoring, storage, and job submission. By developing the testbed and making it available to the research community, we hope to help spur innovation in cloud computing and catalyze the  development of an open source stack for the cloud. In addition to presenting Open Cirrus, this talk will also include a number of important research effort currently undergoing in Open Cirrus, such as Cloud Sustainability Dashboard, OpenNet, ExaScale Data Center, Mercado (Cloud Services market Places), Federation of Open Cirrus and Planet Lab/GENI, etc.

And the second is the Workshop of the Galician Network of HPC, here in Vigo, on Friday:

Aplicaciones de la Supercomputación

Programa

Fecha: 21 de Mayo de 2010
Lugar: Salón de Actos del Edificio de Ciencias Experimentales, Campus Universitario, Universidad de Vigo, Vigo

Horarios

09:50 Apertura y presentación del WorkShop e invitados

10:00 Iain S. Duff - STFC Rutherford Appleton Laboratory, Oxfordshire, UK and CERFACS, Toulouse, France
Título: The solution of really large linear systems arising from discretizations of three-dimensional problems

10:45 Alexandros Stamatakis - Technische Universität München, Germany
Título: Orchestrating Phylogenetic Likelihood Computations on Parallel Architectures

11:30 Coffee Break

12:00 Andrew Gettelman - National Center for Atmospheric Research, Boulder, CO, USA
Título: Simulating Earth's Climate and Chemistry with the Earth's Biggest Computers

12:45 Clausura del WorkShop

Communication package between R and Mesquite

Information just received from the R-sig-phylo mailing list:

We'd like to announce the beta release of packages for communication between Mesquite and R. Mesquite is a graphical application for phylogenetic and evolutionary analysis; R is a system for statistical computation primarily oriented around text-based programming. We have enabled communication in both directions:

• RMesquite enables R programs to make use of Mesquite, either as a graphical interface for editing trees and data, or to provide its broad array of phylogenetic calculations to R (http://rmesquite.r-forge.r-project.org).
• Mesquite.R enables Mesquite to make use of functions in R (http://mesquiteproject.org/packages/mesquite.R/MesquiteCallsR/MesquiteR.html). At the moment these include functions in the R packages ape and diversitree.

Only a handful of functions have been enabled in each direction; we seek your input as to what functions would be of most interest to R users and Mesquite users.

You may consider this as an experimental release for thrill-seekers. Please tell us if something doesn't seem to work or is confusing -- feedback is much appreciated. We hope to continue to strengthen the links between R and Mesquite.

Wayne Maddison, UBC
Hilmar Lapp, NESCent

More on the microbial encyclopaedia

Yesterday (depending on your GMT) I commented about a very nice article on Nature, but forgot to include a few links discussing the work:

• Biologists rally to sequence 'neglected' microbes (Nature news from 17 November 2009, behind a paywall)
• Microbial encyclopaedia guided by evolution (Nature news from 23 December 2009)
• Choice genomes sequenced (Nature editor's summary from 24 December 2009)
• Filling in the evolutionary blanks, genome by genome (blog post by Iddo Friedberg)
• Presenting a genomic encyclopedia of bacteria (and archaea) (Ars Technica article)
• the homepage for the Integrated Microbial Genomes - Genome Encyclopedia of Bacteria and Archaea Genomes (IMG/GEBA) database
• torrent file for current GEBA data at biotorrents (keep it cool, IP maximalists, it's legit)

Jonathan Eisen has a more complete list of links, together with the story behind this paper - read it, it's long but certainly inspiring.

How many microbes live on Earth?

Jonathan Eisen posted on his twitter an  interesting news on BBC about his most recent publication on Nature ("A phylogeny-driven genomic encyclopaedia of Bacteria and Archaea", Nature 462:1056-1060). First of all, congratulations for the nice work! Since the original BBC article is in Spanish, I have tried to translate it here. You will soon realize that neither English nor Spanish are my first languages; I'll fix the mistakes as they are spotted by someone, and I assume responsibility for the remaining errors.

Scientists from US and Germany presented the first issue of the Genomic Encyclopedia of Bacteria and Archaea (GEBA) that collects all living microorganisms on Earth.

It is expected that the publication - whose details appear on Nature Magazine - help researchers to better understand the several roles played by the microorganisms on this planet. It is estimated that the Earth harbors around one nonillion (1 followed by 30 zeros) microbes and despite around 2000 microorganisms already have their genomes deciphered, a large number remains unexplored. The Encyclopedia is being compiled by the Joint Genome Institute under the US Department of Energy, and the German Collection of Microorganisms and Cell Cultures.

Only single-celled ones

"This is a rich sample of the diversity of microbe genomes" says professor Jonathan Eisen, main author of the investigation. "To rely on a better sampling of the whole tree of life give us a better reference point to predict gene functions" he adds. The encyclopedia includes all prokaryotic organisms of the planet, which means the unicellular organisms. Unlike eukaryote organisms like us, yeast and the fungi, the prokaryotic cells don't have a membrane covering their DNA. This organisms are divided in two large groups: the Bacteria, which include the small minority of pathogens that makes us sick, and the Archaea, which are organisms that can survive in extreme environments like thermal waters. Up until now there have been sequenced around one thousand prokaryotic genomes. Almost all of them are pathogenic organisms.
According to professor Eisen "it has been like tracing a world map and including only three cities". Now the new encyclopedia analyzes the main representatives of the big branches of the prokaryotic family tree and the present study shows 56 genomes of this group. As explained by the scientists, even though it is known that microbes can exchange genes with other species (a process called lateral transfer) their position in the family tree, called phylogeny, is more important when we want to pinpoint where new genes appear and how they spread.

The beginning

"Microbes are mediators in almost all known biological processes of the planet" says professor Eddy Rubin, project leader. "And the sequencing of their genomes have revolutionized our understanding of the diverse roles they play". The information obtained with this first group of 56 organisms, adds the scientist, may help researchers in improving processes like biofuel production, bioremediation (to "clean" contaminated surroundings), and the way by which carbon is sequestered in the environment. According to the investigators, this is just the beginning of the project and they expect to be able to sequence all the diversity of microorganisms on Earth, including the hundreds or maybe thousands of microbe genomes currently unknown.  "The known phylogenetic diversity of Bacteria and Archaea is huge, with hundreds of big lineages and probably millions or hundreds of millions of species" says professor Eisen. "This encyclopedical project is starting from the top - with the big phylogenetic groups - with 100 genomes from all tree. "But we are just scratching the surface in the characterization of Earth's diversity" adds the researcher.

My only dispute in this article is that they lead to the impression that all single-celled organisms are prokaryotes. Yes, they fix that in the next sentence when they mention yeasts - which are (mostly?) unicellular - as eukaryotes, but then (unless my semantic interpretation is wrong) they introduce another misunderstanding since yeasts are fungi. But now I understand how hard it must be to convey concepts like phylogeny or Archaea to a broad audience. And I am not sure if "leader" is the best translation for "director"...

Recent CUDA applications

Taking a look at Nvidia's CUDA zone I found some recent additions - besides important ones that I already knew like the Smith-Waterman and the phylogenetic likelihood algoritihms. Here is a list of these new programs and libraries that take advantage of GPUs:

1. Expectation Maximization algorithm for Gaussian Mixture Models
2. Multilevel algorithm for MDS (multidimensional scaling)
3. Multiclass classifier based on SVMs (support vector machines)
4. GPU computing in the R statistical environment (BLAS lowlevel routines and dist(), hclust(), cor(), and granger.test() functions)
5. Smith-Waterman algorithm for sequence database search
6. Quicksort library
7. Feature finding algorithm for mass spectrometry
8. Smith-Waterman algorithm for sequence alignment
9. MDR (multifactor dimensionality reduction) algorithm for detecting genetic epistatic interactions (white paper)
   

The last reference is just a two-page summary, and the 8th reference is behind a paywall - I couldn't access it myself - but the slides are available here.

Powered by ScribeFire.

Phylogenetics, by Joe Felsenstein

Luke J. Harmon and Dan Rabosky recently e-enterviewed Joe Felsenstein. Here are some interesting points:

Luke: What are the most exciting recent developments in systematics / comparative methods?

Joe: The availability of genome-scale information is certainly one. The arrival of a generation of young researchers who are comfortable with statistical and computational approaches is another. But the most important development is reflected in recent work on coalescent trees of gene copies within trees of species. What this does is tie together between-species molecular evolution and within-species population genetics. Those two lines of work have been developing almost independently since the 1960s. But now, with population samples of sequences at multiple loci in multiple related species, they are coming back together. This is not another Modern Synthesis, but it is a major event that needs a name. How about the "Family Reunion"? Long-estranged relatives who have not been in touch are getting together.

(...)

Luke: What do you think about the current trend in phylogenetics (and, lately, comparative biology) towards Bayesian approaches?

Joe: I am a curmudgeon on this, in that Bayesian approaches do not feel right to me. So I have been resisting them. Bayesians were unhappy with the treatment of Bayesian Inference in my book, in that I did not give them four chapters, the last of which ended by declaring victory. I think we're all Bayesians when we come to cross the street, balancing evidence of approaching cars against our priors. But that's where one of the criticisms of Bayesianism comes in -- do we all have the same priors? Is there necessarily a single prior that you can use that will be broadly acceptable to your readership? If not, then maybe the reader of the paper should instead be given the likelihood curve so they can apply their own prior to it. For phylogenies, priors giving equal probability to all topologies (or to all labeled histories) would be noncontroversial. But the part of the prior that puts distributions on branch lengths could be wildly controversial. There is also the issue of whether some things, such as whether the sun will rise tomorrow morning, really should have a prior.

People should be Bayesians if that fits with their philosophy of doing science. But not just because a Bayesian program happens to run faster than a non-Bayesian one. They should also realize that we will continue to have both Bayesians and non-Bayesians. Biologists sometimes think that this controversy emerged in their field and will be settled there -- that one more really good argument and everyone will become a Bayesian. They might not be aware that Bayesian arguments have been around since 1764. There is no new decisive argument that's going to arise in our field.

The issue to contemplate is the priors, not the details of MCMC techniques. We have not yet seen a case where an important conclusion depends strongly on what prior you assume. Perhaps we never will, but if a case like that arises, and causes trouble for Bayesian approaches, people should not be too surprised.

The commentaries are also very enlightening.

Powered by ScribeFire.