Una comparación de lenguajes de programación usados en bioinformática

Por Mathieu Fourment y Michael R Gillings. Traducido por Germán González



Los análisis bioinformáticos involucran una amplia gama de de tareas y procesos. Se han escrito diversos programas para varias aplicaciones bioinformáticas usando cada lenguaje disponible. A causa del tamaño de los conjuntos de datos en bioinformática, el tiempo computacional no es trivial y es deseable la eficiencia en la velocidad computacional. Se han publicado comparaciones de la precisión del algoritmo de diferentes programas que se encargan de tareas similares [1-7], permitiendo la evaluación de los mejores algoritmos para usar en tareas específicas. Sin embargo, es posible que el mismo programa, escrito en diferentes lenguajes, o ejecutándose bajo diferentes sistemas operativos, pueda exhibir diferencias significativas en velocidad y eficiencia. Hay, en este momento, pocos datos directos sobre la velocidad y la eficiencia subyacente de algoritmos equivalentes escritos en diferentes lenguajes. Mientras que los lenguajes mismos han sido comparados, tales comparaciones no se han realizado usando algoritmos que son relevantes para la bioinformática [8].

Un típico programa de bioinformática lee archivos FASTA, mantiene las secuencias de ADN en memoria, realiza diferentes tareas computacionales sobre las secuencias y finalmente escribe el resultado en otro archivo. Otra tarea común en bioinformática es la minería de textos o parseo de textos. Pueden generarse grandes cantidades de datos en diferentes formatos. Como los formatos de archivo pueden ser diferentes, unir los programas en un solo trámite es difícil, por lo tanto se escriben scripts para que actúen como interfaces entre los programas realiando las partes secuenciales del análisis. Los scripts son también usados para extraer información de grandes archivos de datos, mejorando así la presentación de los resultados. Estos scripts rápidos son usualmente implementados en Perl o Python. Por consiguiente, cualquier procedimiento bioinformático tiene un cierto número de áreas donde la programación puede ser mejorada, estas son: el espacio requerido temporalmente para almacenar datos, la velocidad de computado, la vinculación entre programas y la presentación de análisis.

En este artículo examinamos tres tareas usadas comúnmente en biología, el algoritmo Sellers [9], el algoritmo Neighbor-Joining NJ [10] y un programa de parseo de las salidas de BLAST [11]. En cada caso probamos los programas usando diferentes lenguajes. Esta comparativa (benchmark) fue realizada en Linux y Windows, ya que las computadoras utilizadas tenían un doble booteo. Hay varias razones para realizar este ejercicio de comparativa. Específicamente queremos determinar si C puede ser más rápido que Java para realizar detección de recombinación, que es un ejercicio computacional inherentemente difícil.

También queremos examinar los requerimientos de memoria de cada combinación de programa y lenguaje, ya que si bien la capacidad de la memoria se incrementa constantemente y el hardware se vuelve más barato, los grandes conjuntos de datos en el análisis bioinformático pueden ser un problema para las computadoras de escritorio. También queremos comparar un lenguaje de script, como Perl, con lenguajes compilados como Java y C. Para completar la comparación también se incluyeron lenguajes “rivales”. Esto incluye a C++, C# y Python. Los lenguajes seleccionados para este estudio fueron elegidos sobre la base de que estos eran los más populares y frecuentemente usados para aplicaciones biológicas.

Perl y Python son a menudo llamados lenguajes de script y cuando son ejecutados, son compilados en una presentación intermedia sin crear un archivo intermedio (árbol de sintaxis en Perl y código de byte en Python) y luego interpretados. Ambos lenguajes usan un sistema de gestión automática de la memoria y tienen grandes bibliotecas libres. Son apropiados para web scripting (por ejemplo, CGI), análisis e implementación de trámites como Inter-ProScan [12].

C y C++ son lenguajes completamente compilados, adecuados para tareas intensivas de sistema.

Java y C# son lenguajes semi compilados que usan un sistema de gestión automática de memoria. Un programa Java es compilado en un código de nivel intermedio o código de byte (bytecode) que luego es ejecutado por un interprete o por un compilador en tiempo de ejecución, en este caso, la Máquina Virtual Java (JVM). En C# el código de nivel intermedio se llama Microsoft Intermediate Language ye es ejecutado en el entorno .NET Common Language Runtime.

Proyectos voluntarios han producido bibliotecas o módulos para biólogos. Las proyectos de código abierto más comunes, los cuales están incorporados en la Fundación Open Bioinformatics, son BioPerl, BioPython y BioJava [13].

Resultados

Los lenguajes que investigamos pueden ser divididos en tres grupos: el grupo de script de Perl y Python, el grupo de semi compilados de Java y C# y del grupo de compilados de C y C++.

En primer lugar comparamos los lenguajes dentro de los grupos, luego comparamos los grupos entre sí (Fig. 1,2,3,4) y finalmente comparamos la velocidad en Windows y Linux. En este artículo nos referiremos a la facilidad de codificación como el número de líneas de código que se necesitan para escribir un programa, teniendo en cuenta la disponibilidad de bibliotecas, que es un factor en el número de líneas de código que se necesitan para compilar un programa.


Perl versus Python

Perl tiene un rendimiento claramente superior al de Python para operaciones de entrada/salida. Perl fue tres veces más rápido que Python leyendo un archivo FASTA y necesitó la mitad de espacio para guardar las secuencias en memoria (Fig. 4). De los resultados de los alineamiento globales y de los programas NJ parece que Python tiene más capacidad para la manipulación de cadenas de caracteres.

Aun si el programa NJ requiere leer un archivo, donde Python no tiene un buen desempeño comparado con Perl (Fig. 2), la tarea más exigente fue realmente el cómputo de la matriz de divergencia, ya que más del 90% del tiempo de procesamiento fue ocupado en esta etapa en cada lenguaje excepto en C, donde tomó más del 75% del tiempo de procesamiento. Python tuvo el peor desempeño en el parseo de un archivo BLAST (Fig. 3), tomando más de 38 minutos para procesar el archivo, comparado con Perl, que tomó solamente 7,28 minutos. La diferencia no surge de alguna incapacidad de Python para manejar archivos grandes, ya que tomó solo 3,2 minutos para leer el archivo sin procesar las líneas. Perl completó la misma tarea en solo 1,4 minutos.

Perl hace hincapié en el respaldo para tareas comunes orientadas a aplicación, teniendo expresiones regulares incorporadas, escaneo de archivos y características de generación de reportes. Python hace hincapié en el respaldo para metodologías comunes en programación como diseño de estructuras de datos y programación orientada a objetos.

Figura 1. Comparación del velocidad del programa de alineamiento global
Comparación del velocidad del programa de alineamiento global usando una penalidad por hueco de 10 implementado en C, C++, Java, Perl y Python. Los programas fueron ejecutados en Linux y en Windows. Se usaron dos secuencias de ADN de 3216 pb y 3217 pb.


Java versus C#

C# parece requerir menos memoria que Java para mantener cadenas de caracteres en memoria, como demostramos cuando leímos secuencias de ADN de un archivo (Fig. 4). C# tambien necesita menos tiempo para leer este tipo de archivos. Interesantemente, Java fue ligeramente más rápido en el programa de alineamiento global (Fig. 1) pero mucho más lento en el programa NJ (Fig. 2). La implementación de expresiones regulares en Java parece que supera a C# (Fig. 3). Esta diferencia no surge de alguna incapacidad de C# para manejar archivos grandes, ya que lee estos archivos más rápido de lo que lo hace Java. Java necesita 3.2 minutos mientras que C# toma solo 2.8 minutos para leer el mismo archivo.

Figura 2. Comparación de velocidad del programa Neighbor-Joining
Comparación de velocidad del algoritmo Neighbor-Joining usando el modelo evolutivo de Jukes-Cantor implementado en C, C++, C#, Java, Perl y Python. Los programos fueron ejecutados en Linux y Windows. El archivo de entrada fue un alineamiento de 76 secuencias de ADN.


C versus C++

El rendimiento de C y C++ fue muy similar (Fig 1, 2, 3, 4). Esto quizás no sea una sorpresa ya que C++ es una extensión de C. Cuando un programa C fue compilado con el compilador de C++ obtuvimos resultados casi idénticos, pero cuando se usaron las bibliotecas estándar de C++ (como por ejemplo las cadenas caracteres) el rendimiento tendió a deteriorarse ligeramente. Es importante prestar atención a que la tokenización fue dos veces más rápida que las expresiones regulares para analizar el mismo archivo BLAST, pero tomó más tiempo escribir el programa utilizando tokens.

Figura 3. Comparación de la velocidad del programa de parseo de BLAST
Comparación de la velocidad del programa de parseo de BLAST implementado en C, C++, C#, Java, Perl y Python. Los programas fueron ejecutados en Linux y Windows. El archivo de entrada fue un fichero de 9.8 Gb de una ejecución de BLASTP.


Grupo versus grupo

El ejemplo de alineamiento global demostró que los lenguajes semi compilados (Java y C#) fueron casi tan rápidos como el grupo compilado (C y C++), mientras que los lenguajes interpretados (Perl y Python) fueron seis veces más lentos (Fig. 1). En el programa NJ, el rendimiento de C# fue similar al de C y C++, mientras que Java tomó significativamente más tiempo (Fig. 2).La mayor desventaja de los lenguajes semi compilados es su uso de memoria, ya que requieren cerca de 20 veces más memoria que C y 3 veces más memoria que Perl (Fig. 4).

Java y C# parecerían ser un solución media entre la velocidad de C/C++ y la facilidad de codificación de Perl/Python.

Sorprendentemente, Java tuvo un mejor rendimiento que Perl durante la comparativa de expresión regular.
En Java es posible embeber código C para mejorar la eficiencia del programa usando extensiones de Java Native Interface (JNI). El equivalente en Perl sería la extensión eXternal Subroutine (XS). Por ejemplo, el núcleo del programa NJ fue escrito en Perl, pero cuando la subrutina calcula una comparación de pares fue escrito en C, esto aceleró el programa de 11.8 segundos a 0.29 segundos. JNI mejoró su velocidad en menor medida, de 2.58 segundos a 0.71 segundos. Cualquier pérdida de portabilidad fue compensada por la ganancia en rendimiento, ya que no fue necesario reescribir el programa completo.

Figura 4. Comparación del uso de memoria de los programas Neighbor-Joining y alineamiento global
Comparación del uso de memoria de los programas Neighbor-Joining y alineamiento global implementados en C, C++, C#, Java, Perl y Python. Los programas fueron ejecutados en Linux.


Windows versus Linux

El rendimiento relativo de los lenguajes probados no cambió en Windows pero el rendimiento total cambió dependiendo del programa comparado. Solo C# y Python parecieron consistentemente rápidos en cada programa en Windows. En el programa de alineamiento global todas las implementaciones funcionaron mejor en el entorno Windows (Fig 1). El programa NJ (Fig 2) y el parseador BLAST (Fig 3) realizados en C y C++ fueron más lentos en Windows, mientras Java y Perl fueron más rápidos que en Windows en el ejemplo NJ (Fig 2) pero más lentos en el ejemplo del parseador BLAST.

La comparación entre Linux y Windows debe ser cuidadosamente interpretada, ya que las implementaciones del compilador son diferentes, así como el sistema operativo que las ejecuta. Al final, los factores críticos son la velocidad y la utilización de memoria, ya que el usuario está buscando rendimiento en los programas, no generalmente en el SO o en los compiladores.


Caso de estudio: Servidor BLAST

Un programa rápido y eficiente en el uso de la memoria puede hacer una diferencia significativa cuando se ejecuta en un servidor público como BLAST, que es consultado millones de veces al día. La elección obvia para tal programa de computación intensivo era usar C con Perl CGI para la interfaz web. Si consideramos que Perl fue cerca de 60 veces más lento que C en la comparativa de alineamientos globales y que una secuencia de consulta de 3500 nucleótidos contra la base de datos no redundante toma aproximadamente 10 segundos (incluyendo la transferencia a través de la web), entonces su la consulta es realizada un millón de veces durante el día, el tiempo computacional total se incrementaría 60 veces, tomando considerablemente más tiempo de servidor. La misma observación se podría aplicar al uso de memoria. Después de la elección del lenguaje apropiado de programación, también es importante mejorar el algoritmo base. Nuevos algoritmos para analizar relaciones filogenéticas han reducido el tiempo computacional de semanas a días, o incluso horas [14].

Discusión

Todos los programas examinados aquí fueron escritos por el mismo programador con diferentes niveles de experiencia en Java, Perl y C++. Los otros lenguajes fueron implementados mientras se los aprendía. A pesar de que la semántica de estos idiomas es similar, ya que C influyó en C++, C#, Java, Perl y Python, directa o indirectamente, la filosofía de algunos de los lenguajes es diferente y los programas deben implementarse de acuerdo con el paradigma del lenguaje. Por ejemplo, los programadores de Perl prefieren las tablas hash a los arreglos, junto con un bucle que es más ampliamente utilizado en C. Es también importante tener en cuenta que la función de hash puede ser costosa cuando se añade un nuevo valor y la memoria asignada sería mayor que un arreglo que contiene el mismo número de elementos. La ventaja de una tabla hash es el velocidad en la recuperación de algunos datos, pero debe evitarse una tabla hash cuando el programador tiene que examinar secuencialmente todos los valores, debido a los costes adicionales que se producen al añadir el par de valores clave. En el algoritmo Perl NJ una implementación que utiliza un arreglo para almacenar las secuencias parecía ser más rápida y más eficiente en el manejo de la memoria que un programa que utiliza una tabla hash. Por lo tanto no se usaron tablas hash en esta comparativa. Hay un importante compromiso entre rendimiento y conveniencia. Perl y Python permiten la lectura y la carga de un archivo en la memoria en una declaración. Si bien este enfoque es conveniente frente a la lectura y el procesamiento de un archivo línea por línea, el sistema operativo podría comenzar a cambiar la memoria, frenando así todo.

La creación de objetos, recolección de basura y reciclaje de la memoria son costosos en términos de uso de CPU y memoria, por lo tanto, se deberán adoptar algunas precauciones al crear los objetos y el número de objetos debe reducirse lo más posible. Para evitar fugas de memoria o aplicaciones pesadas, los objetos también deben ser reutilizados cuando sea posible y se deben evitar los objetos inalterables como el objeto String en Java, sobre todo cuando los objetos temporales se crean en rutinas de uso frecuente. Los objetos en C# y Java ocupan más memoria que en otros lenguajes orientados a objetos como C++ debido a su habilidad para utilizar la reflexión. La reflexión es una poderosa herramienta que contribuye a la flexibilidad de estos dos lenguajes. Sin embargo, esta característica sólo debe ser utilizada cuando sea necesario, ya que llamar al método de reflexión tiene un costo considerable en el desempeño, hacen que el código sea más difícil de comprender y los errores se encuentran en tiempo de ejecución en lugar de en tiempo de compilación.

La manera en que se accede a los objetos y se almacenan en la memoria influye en el rendimiento de cada lenguaje. C++, C# y Java almacenan los objetos como un bloque de datos y acceden a ellos mediante compensaciones constantes, mientras que los objetos en Python se implementan como tablas hash. Hay varias formas de crear objetos en Perl. Pueden utilizarse diferentes estructuras de datos, pero la mayoría de los programadores usan hashes, a pesar de que los arreglos son más rápidos, evitan las colisiones y usan menos memoria.

Cabe señalar que la implementación de Perl del algoritmo NJ fue mejorada sustancialmente por la conversión de cada secuencia a un arreglo en lugar de utilizar la función substr en la cadena de caracteres para el cálculo de la matriz de similitud. Aunque el programa fue un 10% más rápido, la memoria se incrementó diez veces.


Expresividad

El número de líneas en un programa varía de un programador a otro, y también en su disposición a acortar el código en detrimento de la legibilidad. Es importante destacar que no es posible encontrar una correlación entre la expresividad y el rendimiento.
Sin embargo, una diferencia notable se observó (Fig. 5), especialmente con expresiones regulares. En Perl, una única declaración se puede usar para detectar un patrón y el patrón capturado se recupera con la variable especial $1, mientras que en Java el programador tiene que crear una instancia del objeto Pattern que es una representación compilada de la expresión regular, y luego crear un objeto Matcher que realiza operaciones de apareamiento en una secuencia de caracteres, interpretando el objeto Pattern. Los siguientes ejemplos ilustran la recuperación de un número GI de un archivo FASTA:

Perl:
print $1 if($string =~/^>gi\ |(\ d{3,})/);

Java:
Pattern p = Pattern.compile(“^>gi\ |(\ d{3,})”);
Matcher m = p.matcher(string);
if(m.find()) System.out.print(m.group(1));

Figura 5. Número de líneas de cada programa
Número de líneas para los programas de alineamiento global, parseador BLAST y Neighbor-Joining, implementados en C, C++, C#, Java, Perl y Python.

Las filosofías de los lenguajes con frecuencia explican las diferencias en relación a la expresividad y la legibilidad de los lenguajes. Por ejemplo, la filosofía de Python es tomar el enfoque más claro, más simple y sencillo para escribir un programa y aceptar la penalidad de rendimiento resultante.

Mientras que Perl ofrece más libertad al programador resultando, en algunos casos, en programas que son ilegibles para los que no son programadores de Perl.

Factores tales como el rendimiento y uso de memoria son importantes, pero no tiene por qué ser el único factor determinante cuando se elige un lenguaje. Ya que la gestión del tiempo es también un factor importante, un lenguaje puede ser elegido por su biblioteca, la futura escalabilidad, comunidad activa y la interfaz a otros lenguajes.

Si bien es difícil definir una curva de aprendizaje para cada lenguaje, se puede encontrar ventajas y desventajas de cada uno. La gestión de memoria, tal como la asignación de memoria hace más fáciles las tareas para los programadores de Java, C#, Perl y Python, aunque el uso de memoria siempre debe estar bajo control. El uso de punteros en C y C++ puede ser abrumador para un alumno, y puede tomar algún tiempo para dominar su uso. Python está diseñado para ser un lenguaje muy legible, con frecuencia usando palabras clave en Inglés, mientras que los otros cinco lenguajes usan signos de puntuación.

La independencia de plataforma puede ser un factor para elegir un lenguaje y también puede facilitar su aprendizaje. Java utiliza una máquina virtual para funcionar en diferentes sistemas operativos y como Perl y Python se almacenan en un archivo de texto y no en un archivo binario, estos scripts pueden ser ejecutados en cualquier computadora que tenga el intérprete adecuado.

La diversidad y el tamaño de la biblioteca estándar de Java, Python y C# es una gran ventaja en comparación con los otros lenguajes, incluyendo conjuntos de clases para crear interfaces gráficas, estructuras de datos (vectores, tablas hash, pilas, colas), expresiones regulares, acceso a bases de datos y redes.

A pesar de que la biblioteca estándar de Perl parece menor en comparación con la de Java, Python y C#, se beneficia de una gran comunidad de programadores que crean módulos recogidos por la red CPAN [15].

C tiene una biblioteca estándar muy limitada que soporta flujos de entrada y salida, asignación de memoria, matemáticas, cadenas de caracteres, y valores de tiempo. La biblioteca de C++ contiene la biblioteca de C, así como una clase para manipular cadena de caracteres y la biblioteca estándar de plantillas (STL) que contiene tanto los contenedores o estructuras de datos como los algoritmos, una biblioteca de cadenas de caracteres mejorada y librerías de entrada/salida de flujo.

Como se indicó anteriormente en el ejemplo de alineamiento global, Java y Perl puede comunicarse con un programa escrito en C, aumentando la velocidad del programa usando JNI y XS, respectivamente.
Por ejemplo, si un programa de computadora basado en comandos escrito en C necesita una interfaz gráfica, una solución fácil sería usar la biblioteca Swing y el marco JNI en lugar de reescribir todo el programa en Java. La posibilidad de una interfaz lenguaje a lenguaje es muy útil cuando algún código ya está escrito en uno de ellos.

Así como C, el marco JNI permite a Java interactuar con C++ y Fortran. La desventaja de este enfoque es
la pérdida de portabilidad. Java también pueden interactuar con Python usando Jython, que es una implementación de Python en Java.

Algunas tareas bioinformáticas, tales como cargar un archivo FASTA o parsear un archivo BLAST, se realizan con tanta frecuencia que tiene sentido la reutilización de código mediante la creación de bibliotecas o módulos.
Muchos programadores producen módulos para la comunidad bioinformática y ponen a disposición a través de sus sitios web. Las bibliotecas más utilizadas son BioPerl, BioPython y BioJava. Estos proyectos de código abierto pertenecen a la Fundación Open Bioinformatics y proporcionan herramientas con múltiples funcionalidades que facilitan la creación personalizada de trámites o análisis.

Lamentablemente no están disponibles bibliotecas con este nivel de organización y diversidad para C, C++ y C#, aunque algunas pequeñas bibliotecas están disponibles de forma independiente [16,17] .

En este artículo nos centramos en el desempeño de los lenguajes, no en el rendimiento de las implementaciones de los algoritmos. Por ejemplo, la velocidad del programa de alineamiento podría mejorarse mediante el uso de un arreglo unidimensional de tamaño n × m en lugar de una matriz bidimensional de tamaño n × m.
Este enfoque permitiría acelerar la asignación de memoria, pero este no era el objetivo de esta comparativa.

En este artículo, utilizamos herramientas de perfil incluidas en las bibliotecas o usamos opciones de compilación/ejecución para encontrar las implementaciones más rápidas. Los perfiles proporcionan información importante sobre aplicaciones, tales como el uso de memoria y la fracción de tiempo dedicada a cada función. Mediante el uso de perfiles y un enfoque de prueba y error, los programas fueron significativamente mejorados. Se utilizó la biblioteca Devel::DProf en Perl, la opción Xprof en Java, el módulo cProfile en Python, el perfil por defecto en C# utilizando -profile = default y la opción de compilador -pg junto con el programa gprof en C y C++.

Conclusión

Como era de esperar, C fue el mejor en esta comparativa, en términos de velocidad y uso de memoria. Pero para lograr dichos rendimientos en general requiere más código a causa de su reducida biblioteca estándar. Esta comparativa es sólo una prueba preliminar con un número limitado de tipos de análisis. Las comparaciones utilizando diferentes programas pueden cambiar el rendimiento relativo de los lenguajes. Las interfaces gráficas son muy importantes en biología, por lo tanto, sería interesante comparar las bibliotecas disponibles.

La elección del mejor lenguaje para una tarea será de acuerdo con la filosofía original, teniendo en cuenta que Java es un lenguaje portable orientado a web, Perl es un poderoso lenguaje de script, Python es un lenguaje fácilmente codificado y C y C++ son eficientes lenguajes utilizados en sistemas operativos y drivers.

Los rendimientos también pueden variar en función del compilador y la versión utilizada. Sun está mejorando constantemente el compilador e intérprete de Java y otras implementaciones de JVM también están disponibles como la de Kaffe [18] y la de IBM.

La principal motivación para realizar esta comparativa fue comparar un programa de detección de recombinaciones en Java y C. El programa de recombinación escrito en Java se ejecutó en 11 minutos y la nueva versión en C se ejecutó en 9 minutos con el mismo conjunto de datos y los mismo parámetros. Esta prueba involucró algunos cientos de secuencias y un único gen objetivo. Dada la rápida mejora en las tecnologías de secuenciamiento de alto rendimiento, es probable que en el futuro se lleven a cabo pruebas que impliquen órdenes de magnitud de más secuencias. El ahorro en tiempo de cálculo será esencial para que este tipo de análisis sea eficiente.

Métodos

Diseño de la comparativa

Durante el proceso de comparativa, fueron desactivados los procesos innecesarios. Cada programa fue ejecutado tres veces y se registraron el tiempo y el uso de memoria mínimos.

Los programas de C y C++ fueron optimizados con el indicador -O3. No se utilizaron hilos (threads) explícitamente para escribir el programa. Los compiladotes o intérpretes son descritos en la tabla 1.

La velocidad de procesamiento fue medida usando el programa GNU ‘time’ que está presente en la mayoría de las distribuciones de Linux. En este artículo solo presentamos el tiempo del usuario para la salida. Los perfiles fueron usados también para inspeccionar la repartición del tiempo y la asignación de memoria. En Windows, se utilizó
un simple script de Perl para iniciar todos los programas con la opción -Dprof para medir el tiempo de todos los procesos. El uso de memoria fue medido en Linux usando el comando “grep Vm/proc/pid/status”, sólo para los programas NJ y alineamiento global ya que el parseo no usa mucha memoria.

Todos los programas fueron ejecutados con la siguiente máquina con un doble booteo Linux/Windows:

Linux: Fedora core 7, kernel 2.6.21-1.3228
Windows: Windows XP professional, Version 2002, service pack 2
Intel(R) Core(TM)2 CPU 6400 @ 2.13 GHz
4 GB DDR2 memoria
250 GB disco rígido

Tabla 1. Lista de lenguajes con los nombres y versiones de sus respectivos compiladores o interpretes

Linux Windows
Lenguaje Comp./Interprete Versión Comp./Interprete Versión
C GNU gcc 4.1.1 gcc 3.4.2
C++ GNU g++ 4.1.1 g++ 3.4.2
C# gmcs/mono 1.1.17.1 .NET csc 2.0.50727
Java Sun JDK Javac/Java 1.5.0_09 Sun JDK Javac/Java 1.5.0_12
Perl Perl 5.8.8 Active state Perl 5.8.8
Python Python 2.4.4 python 2.5.1


Algoritmos

Algoritmo Sellers [9]

El algoritmo Sellers es un método simple de alineamiento global de secuencias que usa un enfoque de programación dinámica con penalidad por huecos (gaps). Los puntajes para caracteres alineados son calculados (ver ecuación 1) y guardados en una matriz de similitud F con una penalidad por hueco lineal d, y entonces s(i,j) es el puntaje de sustitución para el carácter i y j.

En este ejemplo una matriz bidimensional es usada para guardar los puntajes más altos, con la esquina superior izquierda representando el comienzo de la secuencia y la esquina inferior derecha representando el fin de la secuencia, que es el punto inicial del alineamiento. Para secuencias de tamaños n y m, el tiempo de ejecución del algoritmo es O(nm) y la cantidad de memoria usada es O(nm). Este programa requiere leer secuencias de archivos FASTA, inicializar una matriz bidimensional, comparar caracteres y concatenar cadenas de caracteres. Una subsecuencia de 3216 nucleótidos del segmento L del genoma del Hantavirus [GeneBank:AJ005637] fue usado y entonces se introdujeron manualmente eliminaciones, inserciones y SNPs aleatoriamente a lo largo de la secuencia para generar una segunda secuencia de 3217 nucleótidos. Las secuencias no fueron leídas de un archivo pero fueron fuertemente codificadas para evitar la entrada de flujos, y por lo tanto, centrarse exclusivamente en la asignación de memoria y las manipulaciones de cadena de caracteres.

Método Neighbor-Joining [10]

NJ es un algoritmo para construir árboles filogenéticos basado en la distancia y es probablemente el método basado en la distancia más ampliamente utilizado. El método usa el criterio del mínimo evolutivo y comienza asumiendo un árbol de tipo arbusto que no tiene ramas interiores. Luego combina el nodo i y el nodo j que minimizan la ecuación 2 donde r es el número actual de nodos y d(i,j) es la distancia entre i y j. En cada etapa del proceso dos nodos terminales son reemplazados por un nuevo nodo. Este proceso es repetido hasta que dos nodos son separados por una rama.

El tiempo de ejecución del algoritmo es O(n3) y la cantidad de memoria usada es O(n2).

Este programa requiere leer secuencias de archivos FASTA, inicializar una matriz de divergencia bidimensional a partir de una comparación de un par de secuencias de ADN, y finalmente llevar a cabo el algoritmo de agrupamiento. La asignación de memoria, los flujos de entrada y salida, la manipulación de caracteres y la construcción del árbol son los componentes principales de este programa. Los nodos del árbol fueron implementados como estructuras en C y C++, como objetos en C#, Java y Python y como tablas hash en Perl.

El componente más intensivo computacionalmente es el programa de comparación de pares usado para calcular la matriz de divergencia. En el ejemplo de prueba se usaron 76 secuencias de segmento L de Hantavirus con un alineamiento total de una longitud de 6580 nucleótidos.

 

Parseo de BLAST [11]

BLAST es una herramienta que calcula la similitud de secuencia entre una secuencia de consulta y secuencias alojadas en una base de datos especialmente formateada. Usa una tabla de consulta para hacer coincidir palabras y un método de alineamiento local para extenderlas. En la salida uno puede encontrar la secuencia de consulta alineada a una secuencia similar y estadísticas acerca de la relevancia del alineamiento.

Los resultados de BLAST pueden ser de varios gigabytes y un programa usualmente necesita parsear las partes de interés o alimentar otro programa. Por ejemplo, numerosos programas de Ontología Génica [19] usan salidas de BLAST para asignar términos GO a secuencias desconocidas.

La tokenización puede ser usada para parsear archivos de resultados de BLAST pero esto puede ser tedioso y requiere un buen conocimiento de la estructura de la entrada. Las expresiones regulares hacen más sencillas este tipo de tareas, con el único inconveniente de ser potencialmente más lentas. El programa parsea y muestra en un archivo de una línea separado por comas, que incluye el nombre de la secuencia, el identifcador del gen, el puntaje, el porcentaje de identidad, la evaluación y las coincidencias positivas. En este ejemplo que probamos, la salida fue redirigida a to/dev/null en Linux y a NUL en Windows.

El programa de prueba hace uso de flujos de entrada y de expresiones regulares. Un programa que usa tokenización fue escrito en C como control para comparar con las expresiones regulares.

Un archivo de 9.8 Gb de una búsqueda BLASTP con una secuencia de Caenorhabditis elegans (número de acceso [GeneBank:ABD75716]) fue usado en el programa. Nuestro programa no apunta a comparar el rendimiento de las expresiones regulares de cada lenguaje sino la velocidad general de tal tarea. Como las expresiones regulares usadas son bastante simples y se aplican a cadenas de caracteres relativamente cortas (una línea en un archivo BLAST usualmente no es más larga que 80 caracteres) el programa gastará más tiempo leyendo el archivo que realmente parseandolo.

Para leer un archive grande y sobrepasar la limitación del tamaño de archivo de 2GB se usaron los indicadores “-D LARGEFILE_SOURCE – D_FILE_OFFSET_BITS = 64″ cuando se compiló el código fuente de C y C++.

La biblioteca compatible de expresión regular de Perl [20] fue usada en C y C++ ya que sus bibliotecas estándar no implementan las expresiones regulares.

BMC Bioinformatics 2008, 9:82 doi:10.1186/1471-2105-9-82
Esta artículo está disponible en: http://www.biomedcentral.com/1471-2105/9/82
© 2008 Fourment and Gillings; licensee BioMed Central Ltd.
Este un artículo de acceso abierto distribuido bajo los términos de la Licencia reconocimiento de Creative Commons,(http://creativecommons.org/licenses/by/2.0), que permite el uso irrestricto, la distribución y la reproducción en cualquier medio, siempre que el trabajo original sea apopiadamente citado.

Referencias

1. Raghava GPS, Searle SMJ, Audley PC, Barber JD, Barton GJ: OXBench: A benchmark for evaluation of protein multiple sequence alignment accuracy. BMC Bioinformatics 2003, 4:47.
2. Posada D: Evaluation for detecting recombination from DNA sequences: Empirical data. Mol Bio Evol 2002, 19(5):708-717.
3. McGuffin LJ: Benchmarking consensus model quality assessment for protein fold recognition. BMC Bioinformatics 2007, 8:345.
4. Irizarry RA, Wu Z, Jaffee HA: Comparison of Affymetrix Gene-Chip expression measures. Bioinformatics 2006, 22:789-794.
5. Kuhner MK, Felsenstein J: A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Mol Biol Evol 1994, 11:459-468.
6. Clegg AB, Shepherd AJ: Benchmarking natural-language parsers for biological applications using dependency graphs. BMC Bioinformatics 2007, 8:24.
7. Tompa M, Li N, Bailey TL, Church GM, De Moor B, Eskin E, Favorov AV, Frith MC, Fu Y, Kent WJ, Makeev VJ, Mironov AA, Noble WS, Pavesi G, Pesole G, Regnier M, Simonis N, Sinha S, Thijs G, van Helden J, Vandenbogaert M, Weng Z, Workman C, Ye C, Zhu Z: Assessing computational tools for the discovery of transcription factor binding sites. Nat Biotechnol 23:137-144.
8. Prechelt L: An empirical comparison of C, C++, Java, Perl, Python, Rexx and Tcl. IEEE Computer 2000, 33:23-29.
9. Sellers PH: On the theory and computation of evolutionary distances. SIAM J Appl Math 26:787-793.
10. Saitou N, Nei M: The neighbor joining method: A new method for constructing phylogenetic trees. Mol Biol Evol 1987, 4:406-42.
11. Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic Local Alignment Search Tool. J Mol Biol 1990, 215:403-410.
12. Zdobnov EM, Apweiler R: InterProScan – an integration platform for the signature-recognition methods in InterPro. Bioinformatics 2001, 17:847-848.
13. Mangalam H: The Bio* toolkits – a brief overview. Brief Bioinform2002, 3:296-302.
14. Guindon S, Gascuel O: PhyML – A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood. Systematic Biology 2003, 52:696-704.
15. Comprehensive Perl Archive Network (CPAN) [http://www.cpan.org]
16. Butt D, Roger AJ, Blouin C: libcov: A C++ bioinformatic library to manipulate protein structures, sequence alignments and phylogeny. BMC Bioinformatics 2005, 6:138.
17. BioC++ [http://biocpp.sourceforge.net]
18. Kaffe [http://www.kaffe.org]
19. Conesa A, Götz S, García-Gómez JM, Terol J, Talón M, Robles M: Blast2GO: A universal tool for annotation, visualization and analysis in functional genomics research. Bioinformatics 2005, 21:3674-3676.
20. Perl Compatible Regular Expression [http://www.pcre.org]

Comentarios