On subset seeds for protein alignment

This directory contains experimental datasets, results and associated scripts related to the paper On subset seeds for protein alignment published at the IEEE/ACM Transactions on Computational Biology and Bioinformatics journal. The content is divided into two parts that are related respectively to sections V(D) and V(E) of the paper.

1. Theoretical framework and seed design

For a transitive seed alphabet provided by Alphabet file, the tool Alphabet-prob-generator computes background and foreground probabilities of alphabet letters according to foreground and background frequencies of amino acid pairs derived from Blosum62 matrix. This tool directly generates command line arguments for the Iedera program, in the case of transitive alphabets.

Iedera then searches for good seeds according to a given seed model (transitive subset seeds or vectorized subset seeds) : all the command lines used are in the script Makefile.sh. This script generates all the Seed files containing seeds, their selectivily and sensitivity. The script was run every night during approximately one month period on about 50 computers to obtain the results presented in Section V(D) of the paper.

Tools :

Data :

2. Real data experiments

We used 7 protein alignment databases to estimate the sensitivity of our methods.

The script Matcher.databases.pl simulates the hit criterion for subset seed models and the blastp model. It performs the comparison on multifasta alignments provided by the database, using the seeds provided by part 1..

The script compares blastp seeds at differents scoring thresholds T (ranging from 10 to 13 on the Blosum62 matrix), with the subset seeds of at least equivalent selectivity. Namely, selectivity of subset seed was choseen to be at least 0.996342 when T was fixed to 10, and respectively at least 0.997909, 0.998827 and 0.999355 when T was fixed to 11, 12 and 13 (see the the blastp file). The first set of subset seeds meeting this requirement was selected from the "L16" file of each model   ;   e.g. for the non-tree-transitive model and for T=11, the corresponding seed HC01GE,J0B9K,L0GL,KJ0J,LGL of selectivity 0.997968 was taken (see the corresponding file).

Scripts for converting native formats of the databases into multi-fasta format can be found here.

We also provide results obtained for each seed model on each database in the following Match files. Resulting plots can also be found in linear and more readable and unbiased log form in the Gnuplot dir. (svg files can directly been viewed using Firefox, Opera, Safari or Camino browsers).

Tools :

Data :