A tree kernel to analyze phylogenetic profiles

Bioinformatics, vol. 18, p. S276-S284, 2002.

Presented at the 10th International Conference on Intelligent Systems for Molecular Biology (ISMB02), August 3-7, Edmonton, Canada.

Jean-Philippe Vert
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan


The phylogenetic profile of a protein is a string that encodes the presence or absence of the protein in every fully sequenced genome. Because proteins that participate in a common structural complex or metabolic pathway are likely to evolve in a correlated fashion, the phylogenetic profiles of such proteins are often ``similar'' or at least ``related'' to each other. The question we address in this paper is the following: how to measure the ``similarity'' between two profiles, in an evolutionarily relevant way, in order to develop efficient function prediction methods?

We show how the profiles can be mapped to a high-dimensional vector space which incorporates evolutionarily relevant information, and we provide an algorithm to compute efficiently the inner product in that space, which we call the tree kernel. The tree kernel can be used by any kernel-based analysis method for classification or data mining of phylogenetic profiles.

As an application a Support Vector Machine (SVM) trained to predict the functional class of a gene from its phylogenetic profile is shown to perform better with the tree kernel than with a naive kernel that does not include any information about the phylogenetic relationships among species. Moreover a kernel principal component analysis (KPCA) of the phylogenetic profiles illustrates the sensitivity of the tree kernel to evolutionarily relevant variations.

You can download a copy of this paper in various formats:
compressed postscript or PDF

(the original place of publication of this paper is Bioinformatics, the copyright owner is Oxford University Press).

Data used


The SVM and kernel computations are based on the software SVM Light v.3.50 by Thorsten Joachims. We added the following files:

and modified the file:

After compiling SVM Light with the modified files, you should be able to use it with the option "-t 4" (user defined kernel, see the SVM Light documentation).

Warning: the kernel in kernel.c contains the definition of the Bayesian tree model for the particular example studied in this paper. If you want to use it for an other data set, don't forget to modify this file accordingly (or to rewrite it in a cleaner way...).

Useful PERL script


Reproducing the experiments

To reproduce the experiment on your linux machine, download the file tree_kernel.tgz which includes all files described in this page, and do:

% tar xvzf tree_kernel.tgz
% cd tree_kernel/perl/
% ./test.pl

It should take a while. When the experiments is done, check the results in the "result" directory.

Known issues/bugs

The goal of this page is to provide the exact data and code that were used in the publication. Please let me know if you discover a bug, I will list them here without changing the files above.

CSS!Valid XHTML 1.0!

Jean-Philippe Vert
Last modified: Fri Dec 20 18:58:24 CET 2002