13 de junio de 2012

Alineamiento con transformadas de Fourier

En 1992 el grupo de Ilya Vakser publicó en PNAS el método fundamental para poder hacer simulaciones de docking de biomoléculas de manera eficiente, disminuyendo considerablemente el tiempo de cálculo aplicando transformadas rápidas de Fourier. Diez años más tarde se publicó la primera versión del exitoso programa de alineamiento múltiple de secuencias MAFFT, del que ya hemos hablado en otras entradas, que aplica ideas similares para el problema de encajar secuencias similares, como se hace al alinear secuencias.

Figura tomada de http://www.ncbi.nlm.nih.gov/pubmed/12136088. donde se muestran dos picos del análisis de Fourier que se corresponden con dos subalineamientos locales.

En esta entrada mi intención es explicar el fundamento de esta técnica recurriendo al lenguaje Octave, la versión open source de MatLab. El código es el siguiente:

 % alineamiento (sin gaps) de secuencias proteicas usando la FFT  
 % escrito en Octave, que es compatible con Matlab   
 % requiere la libreria 'bioinfo'   
   
 clear all  
   
 %% Conversor binario de secuencias   
 %% Parametros:   
 %% 1) longitud de la secuencia S  
 %% 2) longitud del fragmento F (de S)  
 function [S , F] = aa2bits( sequence , fragment )  
   
 % cada residuo se representa por un numero del 1 al 20  
 % http://www.mathworks.com/help/toolbox/bioinfo/ref/aa2int.html  
 [ seq ]= aa2int( sequence )  
 [ frag ] = aa2int( fragment )   
   
 % codificamos residuos como cadenas binarias de ancho fijo (20 columnas)  
 S=[];  
 for i=1:length(seq)  
   % cada residuo ocp  
   S=[S ones(1,seq(i)) zeros(1,20-seq(i)) ];  
 end  
   
 F=[];  
 for i=1:length(frag)  
   F=[F ones(1,frag(i)) zeros(1,20-frag(i)) ];  
 end  
   
 % completa F hasta igualar la longitud de S  
 F=[F zeros(1,length(S)-length(F))];  
   
 endfunction % no se usa en Matlab  
   
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
   
 % define la secuencia S y el fragmento F que queremos alinear  
 sequence = 'SDEVRKNLMDMFRDRQAFSEHTWKMLLSVCRSWAAWCKLNNRKWFPAEPEDVRDYLLY';  
 fragment = 'KMLNSVCRSWWWWC';  
   
 % convertimos ambas secuencias en dos segnales binarias,  
 % de manera que cada residuo se representa por un natural del 1 al 20  
 [S , F] = aa2bits(sequence,fragment);  
   
 % calculamos el alineamiento de F con S optimizando la funcion objetivo Fobj,  
 % que en este ejemplo es simplemente el producto (como un AND binario)  
 % obtenido al desplazar F de izq a der sobre S:   
 % producto(n) = sum { F(i) * S(i-n) }  
 %        i   
 % aprovechamos que Fobj se puede expresar por medio de transformadas  
 % de Fourier para reducir las operaciones necesarias (de N^2 a 4NlogN)  
 % https://sites.google.com/site/cartografiaygeodesia/prac7.pdf  
 % http://www.pnas.org/content/89/6/2195.abstract  
   
 FTsec = fft(S);  
 FTfrag = fft(F);  
   
 FTproducto = conj(FTfrag) .* FTsec; % producto termino a termino  
   
 % Deshacemos transformacion y localizamos valor maximo,   
 % la posicion que optimiza el alineamiento   
 producto = ifft(FTproducto);   
 [valor maxpos] = max(producto);  
   
 % imprime alineamiento sobre secuencicas binarias   
 tit = sprintf("Optimal alignment, optimal position = %d",maxpos);  
 plot(S*0.75)  
 title(tit)  
 xlabel('sequence position')  
 hold on  
 plot([zeros(1,maxpos) F*0.9] , 'r');  
 axis([0 length(S) 0 1]);  
 legend('sequence','fragment');  
 print -dpng figure_align.png;  
   
 % alineamiento sobre secuencias originales, cambiando maxpos de escala  
 align = printf("Alignment:\nS %s\nF %s%s\n",sequence,blanks((maxpos-1)/20),fragment);  

Como resultado obtendremos un alineamiento como éste, que :
S SDEVRKNLMDMFRDRQAFSEHTWKMLLSVCRSWAAWCKLNNRKWFPAEPEDVRDYLLY
F                        KMLNSVCRSWWWWC
 

Que se corresponde con éste producto de Fourier:



En Perl podríamos usar el módulo Math::FFT para este fin, o la GNU Scientific Library que ya revisamos en otra entrada. Un saludo,
Bruno

5 de junio de 2012

WINTER SCHOOL: ALGORITHMS IN STRUCTURAL BIOINFORMATICS

Hola,
ha llegado a mis manos un anuncio de un curso con contenidos muy cercanos a algunas entradas de este blog e incluso a nuestro material de Algoritmos en Bioinformática Estructural. El curso tendrá lugar en Diciembre en la riviera francesa y acogerá a 20 estudiantes. Os pego los detalles en inglés, el enlace al curso es www-sop.inria.fr/manifestations/algoSB :
 
Dear Colleague,

please find below the announcement for a Winter School on Algorithms
in Structural Bioinformatics: we would appreciate your forwarding it
to PhD students and postdocs who could be interested.

With best regards,
 The organizers :
    Frédéric Cazals, INRIA Sophia Antipolis - Méditerranée
    Juan Cortés, LAAS-CNRS, Toulouse 


%%i%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
ALGORITHMS IN STRUCTURAL BIOINFORMATICS : WINTER SCHOOL
   2-7 DECEMBER 2012, INRIA SOPHIA ANTIPOLIS, FRANCE  
   http://www-sop.inria.fr/manifestations/algoSB/
%%i%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We are pleased to announce a one-week school on Algorithms in
Structural Bioinformatics. The aim is to introduce advanced methods in
this domain, giving special attention to interdisciplinary
approaches. The main focus will be on methodological developments
meant to analyze and predict macromolecular assemblies, as well as on
the corresponding software. The following topics will be taught:

I.   Obtaining and organizing structural information for modeling studies (J. Janin, C. Robert)
II.  Modeling protein complexes and assemblies with Voronoi diagrams (F. Cazals)
III. Molecules as robots: mining the flexibility of proteins (J. Cortés)
IV.  Structural comparisons (R. Andonov, N. Malod-Dognin)
V.   Docking algorithms (C. Prévost, M. Zacharias)

The program will span 5.5 days. The first afternoon will consist of a
mini research symposium during which each participant will present
his/her research interests and achievements.  Each of the five
subsequent days will consist of a lecture (morning session) and a
hands-on computer lab (afternoon session).

Additional information can be found at
http://www-sop.inria.fr/manifestations/algoSB/

INTENDED AUDIENCE. The school is primarily intended for twenty
European PhD students and postdoctoral researchers, but
applications from other parts of the world will also be
considered if space is available.

DEADLINE FOR APPLICATIONS. A one-page application (pdf format) should
be sent by email to algosb-coordinators@inria.fr with Subject "AlgoSB
application", by September 7th, 2012.

The application should provide a mini-vitae or a pointer to the full
vitae, a brief presentation of the applicant's research interests, and
a few lines commenting on expected synergy between one's research and
the courses that will be taught.

Notification of acceptance will be provided by September 30th. It is
expected that all accepted students will participate in the entire
school period.

VENUE AND PARTICIPATION FEES. The Algorithmics in Structural
Bioinformatics school will take place on the French Riviera, at INRIA
Sophia Antipolis - Méditerranée.

The participation fees will be of 390 euros, which include lunches,
coffee breaks, and social events.
 
This school is sponsored by INRIA (http://www.inria.fr/), the CNRS/GDR
Bioinformatique Moleculaire (http://www.gdr-bim.u-psud.fr/), and by
SANOFI (http://en.sanofi.com/).

The organizers :
    Frédéric Cazals, INRIA Sophia Antipolis - Méditerranée
    Juan Cortés, LAAS-CNRS, Toulouse