Proyecto Fin de Carrera de Ingeniería en Informática
Algoritmos de compresión para secuencias biológicas y su aplicación en árboles logénicos construidos a partir de ADN mitocondrial
Pablo Urcola Irache
Directora: Elvira Mayordomo Cámara
Departamento de Informática e Ingeniería de Sistemas Centro Politécnico Superior
Noviembre 2006
Comprimir es comprender Jorge Wagensberg
Agradezco a todo el mundo que me ha ayudado o me ha ofrecido su ayuda en algún momento de la realización de este proyecto su interés y disposición. Como último favor les pido que me dejen dedicar este trabajo a mi abuelo.
Índice general I Memoria
9
1. Introducción
11
1.1.
Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.2.
Alcance
1.3.
Trabajo previo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11 12
1.4.
Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.5.
Métodos, técnicas y herramientas
. . . . . . . . . . . . . . . . . . .
13
1.6.
Contenido de la memoria . . . . . . . . . . . . . . . . . . . . . . . .
13
2. Conceptos previos 2.1.
2.2.
Secuencias biológicas
15 . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.1.1.
Formación de proteínas . . . . . . . . . . . . . . . . . . . . .
16
2.1.2.
Estructura del ADN
. . . . . . . . . . . . . . . . . . . . . .
16
Árboles de logenia . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3. Desarrollo del estudio 3.1.
Adaptación del algoritmo de Lempel-Ziv 3.1.1.
3.2.
19 . . . . . . . . . . . . . . .
19
Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Análisis de los algoritmos de compresión especí cos
. . . . . . . . .
20
3.2.1.
GenCompress . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.2.2.
Pattern Hunter
. . . . . . . . . . . . . . . . . . . . . . . . .
21
3.2.3.
Pattern Hunter II . . . . . . . . . . . . . . . . . . . . . . . .
22
3.2.4.
dnaX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4. Implementación del compresor
25
4.1.
Especi cación del algoritmo
. . . . . . . . . . . . . . . . . . . . . .
25
4.2.
Directivas de diseño . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.2.1.
Sobre los datos
25
4.2.2.
Sobre el uso del algoritmo
4.3.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Estructura del algoritmo . . . . . . . . . . . . . . . . . . . . . . . .
26
4.3.1.
27
Análisis de la entrada . . . . . . . . . . . . . . . . . . . . . .
1
ÍNDICE GENERAL
2
4.3.2.
Selección de las repeticiones
4.3.3.
Codi cación de la salida
. . . . . . . . . . . . . . . . . .
28
. . . . . . . . . . . . . . . . . . . .
29
. . . . . . . . . . . . . . . . . . . . . . .
31
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4.4.
Consideraciones generales
4.5.
Interfaz grá ca
5. Árboles logénicos
35
5.1.
Cálculo de la distancia entre dos secuencias . . . . . . . . . . . . . .
35
5.2.
Características del compresor
. . . . . . . . . . . . . . . . . . . . .
36
5.3.
Métodos de cálculo
. . . . . . . . . . . . . . . . . . . . . . . . . . .
36
5.4.
Herramientas utilizadas . . . . . . . . . . . . . . . . . . . . . . . . .
37
6. Resultados 6.1.
6.2.
39
Resultados del compresor . . . . . . . . . . . . . . . . . . . . . . . .
39
6.1.1.
Banco de pruebas . . . . . . . . . . . . . . . . . . . . . . . .
39
6.1.2.
Análisis de los resultados . . . . . . . . . . . . . . . . . . . .
40
Resultados de los árboles de logenia
. . . . . . . . . . . . . . . . .
43
. . . . . . . . . . . . . . . . . . .
44
. . . . . . . . . . . . . . . . . . . . . . .
44
6.2.3.
Algoritmos y métodos utilizados . . . . . . . . . . . . . . . .
45
6.2.4.
Resultados obtenidos . . . . . . . . . . . . . . . . . . . . . .
45
6.2.1.
Corrección de las pruebas
6.2.2.
Ficheros de prueba
7. Conclusiones
49
7.1.
Conclusiones sobre el compresor . . . . . . . . . . . . . . . . . . . .
49
7.2.
Conclusiones sobre los árboles de logenia
. . . . . . . . . . . . . .
50
7.3.
Conclusiones personales
. . . . . . . . . . . . . . . . . . . . . . . .
51
Bibliografía
53
II Apéndices
55
A. Código fuente de la implementación
57
A.1. Notas de la distribución
. . . . . . . . . . . . . . . . . . . . . . . .
57
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
A.3. ADN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
A.4. Entrada-Salida de Bits (Cabecera) . . . . . . . . . . . . . . . . . . .
60
A.5. Entrada-Salida de Bits
63
A.2. ADN (Cabecera)
. . . . . . . . . . . . . . . . . . . . . . . . .
A.6. Árboles Rojinegros (Cabecera) . . . . . . . . . . . . . . . . . . . . .
67
A.7. Árboles Rojinegros
68
. . . . . . . . . . . . . . . . . . . . . . . . . . .
A.8. Cola de prioridades (Cabecera)
. . . . . . . . . . . . . . . . . . . .
71
A.9. Cola de prioridades . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
A.10.Árbol de rangos (Cabecera)
73
. . . . . . . . . . . . . . . . . . . . . .
ÍNDICE GENERAL
3
A.11.Árbol de rangos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
A.12.Referencias (Cabecera) . . . . . . . . . . . . . . . . . . . . . . . . .
77
A.13.Referencias
79
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.14.Autómata (Cabecera) . . . . . . . . . . . . . . . . . . . . . . . . . .
80
A.15.Autómata
82
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.16.Codi cador (Cabecera) . . . . . . . . . . . . . . . . . . . . . . . . .
84
A.17.Codi cador
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
A.18.Decodi cador (Cabecera) . . . . . . . . . . . . . . . . . . . . . . . .
88
A.19.Decodi cador
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.20.Compresor (Cabecera)
. . . . . . . . . . . . . . . . . . . . . . . . .
89 90
A.21.Compresor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
A.22.Descompresor (Cabecera)
. . . . . . . . . . . . . . . . . . . . . . .
96
A.23.Descompresor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
A.24.Excepciones (Cabecera)
. . . . . . . . . . . . . . . . . . . . . . . .
98
A.25.Excepciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
A.26.Ventana de estadísticas (Cabecera)
. . . . . . . . . . . . . . . . . .
99
A.27.Ventana de estadísticas . . . . . . . . . . . . . . . . . . . . . . . . .
99
A.28.Ventana principal (Cabecera)
. . . . . . . . . . . . . . . . . . . . . 100
A.29.Ventana principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 A.30.Programa principal . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 A.31.Make le
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4
ÍNDICE GENERAL
Índice de guras 2.1.
Procesos de transcripción y traducción
. . . . . . . . . . . . . . . .
16
2.2.
Ejemplo de árbol de logenia de cuatro individuos . . . . . . . . . .
17
4.1.
Fases del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
4.2.
Ventana principal . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4.3.
Ventanas de estadísticas
. . . . . . . . . . . . . . . . . . . . . . . .
32
6.1.
Árbol generado por el algoritmo RLE . . . . . . . . . . . . . . . . .
46
6.2.
Árbol generado por el algoritmo gzip
47
6.3.
Árbol generado por el compresor de cheros de ADN
5
. . . . . . . . . . . . . . . . . . . . . . . . .
48
6
ÍNDICE DE FIGURAS
Índice de cuadros 2.1.
Moléculas y monómeros
. . . . . . . . . . . . . . . . . . . . . . . .
15
3.1.
Ejemplo de construcción de cadena binaria . . . . . . . . . . . . . .
21
4.1.
Codi cación de Bit de Continuidad
. . . . . . . . . . . . . . . . . .
30
6.1.
Banco de pruebas ajeno
. . . . . . . . . . . . . . . . . . . . . . . .
40
6.2.
Banco de pruebas propio . . . . . . . . . . . . . . . . . . . . . . . .
40
6.3.
Prueba t de Student de igualdad de medias 1 . . . . . . . . . . . . .
42
6.4.
Prueba t de Student de igualdad de medias 2 . . . . . . . . . . . . .
42
6.5.
Prueba de igualdad de varianzas . . . . . . . . . . . . . . . . . . . .
43
6.6.
Prueba t de Student de igualdad de muestras
43
7
. . . . . . . . . . . .
8
ÍNDICE DE CUADROS
Parte I Memoria
9
1 Introducción En esta sección se describen los elementos fundamentales en que se enmarca el proyecto como pueden ser el objetivo, el alcance, el trabajo previo en que se apoya, el contexto en que se desarrolla o las herramientas que se han utilizado para su realización. Además se indica de forma abreviada el contenido y distribución del resto de las secciones de la memoria.
1.1. Objetivos Los objetivos del proyecto, tal y como se indicaron en la propuesta, son los siguientes: Estudio de los algoritmos de compresión de secuencias biológicas utilizados en la actualidad, su comparación con los de propósito general y la obtención de unas pautas de diseño que se deben tener en cuenta al crearlos. Estudio de la aplicación de los algoritmos de compresión a la generación de árboles logénicos utilizando la información contenida en el ADN mitocondrial y análisis de las características necesarias de los primeros así como los distintos métodos de construcción de los árboles.
1.2. Alcance De nidos estos objetivos, la intención del proyecto no es superar los niveles de compresión o velocidad de otros algoritmos sino caracterizar de la mejor forma los fundamentos que un compresor de secuencias de adn debiera tener. Finalmente esta caracterización se ha implementado para probar en qué forma mejora los algoritmos existentes.
11
1. INTRODUCCIÓN
12
En relación a los árboles logénicos, éstos no se pueden comparar con otros puesto que hay multitud de versiones válidas y respaldadas cada una de ellas por alguna teoría, así que se considera que se ha alcanzado un resultado bueno al encontrar un método que se aproxima a las ideas más aceptadas en la actualidad por la mayoría. Para la contrucción de los árboles se utiliza la información genética del ADN mitocondrial puesto que debido a su pequeño tamaño se hace más manejable sin perder capacidad de diferenciación entre los distintos individuos.
1.3. Trabajo previo La documentación preexistente tanto en el campo de los algoritmos de compresión como en los árboles de logenia es muy extensa y diversa, aunque, debido a que en general son bastante recientes, la validez de sus contenidos no está muy contrastada, por lo que hay que agudizar el sentido crítico frente a ellos. Existe una gran variedad de algoritmos de compresión genéricos ([13, 12, 20]) y algunos dedicados a secuencias biológicas descritos en [4], [5] y [10], generalmente integrados en las grandes bases de datos de genomas que existen como NCBI
1
o
2
GenBank . Ambos tipos sirven como base para el proyecto puesto que se pretende saber por qué los primeros no funcionan con secuencia biológicas y qué características hacen a los segundos e caces a la hora de comprimir este tipo de datos. En cuanto a los árboles de logenia, la variedad de métodos está relacionada directamente con la diversidad de hipótesis sobre la evolución de las especies, como se explica en [6], y con los distintos métodos numéricos de cálculo de distancias, descritos en [16].
1.4. Contexto El desarrollo de este proyecto se enmarca dentro del grupo de investigación de complejidad computacional (GCC) que forma parte del Grupo de Ingeniería de Sistemas de Eventos Discretos (GISED) del Departamento de Informática e Ingeniería de Sistemas (DIIS). Este grupo investiga sobre el funcionamiento de los distintos algoritmos de compresión de uso general y quería averiguar por qué no eran útiles al comprimir secuencias biológicas. Debido a que se desarrolla en el seno de un grupo de investigación, el proyecto tiene una gran carga de trabajo de recopilación de información y un apartado más reducido de los elementos típicos de un proyecto de software.
1 http://www.ncbi.nlm.nih.gov/
2 http://www.psc.edu/general/software/packages/genbank/genbank.html
1.5. MÉTODOS, TÉCNICAS Y HERRAMIENTAS
13
Este trabajo ha sido parcialmente nanciado por el proyecto de investigación del Ministerio de Educación y Ciencia TIN2005-08832-C03-02, que cuenta con el apoyo de la empresa deCODE genetics.
1.5. Métodos, técnicas y herramientas Gran parte del tiempo de trabajo del proyecto se invirtió en documentación, fundamentalmente lectura de artículos y consulta con otros investigadores que trabajan en el mismo tema. La disposición de los artículos y de algunos algoritmos fue di cultosa en algunos casos debido a las licencias restrictivas, lo que redujo la capacidad de investigación. Una vez conseguida toda la información al alcance, se extrajeron las ideas para la implementación del software desarrollado para posteriormente veri carlo y compararlo con los programas ya existentes. Por último se diseñó un interfaz amigable que facilitara la utilización y la extracción de los datos de la ejecución para su posterior análisis. Además se pudo incluir uno de los algoritmos ya existentes [10] en el mismo interfaz grá co gracias a que se facilitaron los cheros fuentes para su utilización, lo que simpli ca la labor de comparación de ambos algoritmos. El trabajo con los árboles de logenia no se decantaba tanto por la implementación sino por la realización de pruebas y el análisis de los resultados. Por eso 3
se optó por el uso de un paquete de programas
que alcanzara todas las nece-
sidades del proyecto, facilitando el trabajo con los árboles sin necesidad de una implementación propia de los métodos.
1.6. Contenido de la memoria En una primera sección, se de nen los conceptos relativos a secuencias biológicas y árboles de logenia necesarios para la comprensión del trabajo realizado en el proyecto. La sección 3 aborda el proceso de documentación seguido hasta alcanzar el diseño nal del compresor, indicando todos los pasos recorridos y las ideas adquiridas en cada uno de ellos. Posteriormente se profundiza en la mejora implementada utilizando los conocimientos adquiridos en la fase de estudio. La sección 5 está dedicada al trabajo realizado sobre los árboles de logenia. Las dos últimas secciones contienen respectivamente información sobre las pruebas realizadas, los resultados que se obtuvieron y, por último, las conclusiones que se han podido extraer de todo el trabajo realizado.
3 http://evolution.genetics.washington.edu/phylip.html
14
1. INTRODUCCIÓN
2 Conceptos previos En esta sección se explican los conceptos necesarios para entender algunos elementos del proyecto que se alejan de la informática, fundamentalmente relacionados con la genética y con la teoría de la evolución.
2.1. Secuencias biológicas Llamamos secuencia biológica a la representación de cualquiera de la sucesiones de monómeros que intervienen en la síntesis de proteínas a partir de la información genética de los organismos. Se pueden diferenciar tres tipos de secuencias distintas: Ácido desoxirribonucleico o ADN Ácido ribonucleico o ARN Proteínas Cada uno de los elementos básicos que componen una de estas moléculas es un monómero, siendo de distinta naturaleza en cada una de ellas como se aprecia en el cuadro 2.1.
Molécula
Monómero
ADN
Base nitrogenada
ARN
Base nitrogenada
Proteína
Aminoácido
Cuadro 2.1: Moléculas y monómeros
Todas ellas están implicadas en el proceso de extracción de la información genética y su transformación.
15
2. CONCEPTOS PREVIOS
16
2.1.1. Formación de proteínas En el proceso de transcripción, el ADN se utiliza para la síntesis de ARN de diversos tipos. Sin embargo, no toda la información existente en el ADN queda re ejada luego en el ARN. Existen fragmentos, llamados ADN basura, de los que, hoy por hoy, no se conoce funcionalidad alguna. El ARN resultante está exclusivamente dedicado a la generación de moleculas de proteínas. La fase de traducción es en la que se generan aminoácidos a partir de la información contenida en las moléculas de ARN. Para la construcción de un único aminoácido se necesitan tres bases de la secuencia de ARN. Esta traducción se realiza utilizando el llamado código genético por el que se hacen corresponder las tripletas de bases nitrogenadas con aminoácidos. Un mismo aminoácido puede ser sintetizado utilizando la información de distintas tripletas.
Transcripci´on
Traducci´on
adn
arn
proteina
Figura 2.1: Procesos de transcripción y traducción
Desde el punto de vista práctico, el uso del ARN es prácticamente imposible debido a que es un elemento temporal en el conjunto del proceso y su inestabilidad impide su manejo en el laboratorio. Si analizamos el proceso atendiendo a la información almacenada, la fase de traducción implica una pérdida de información al sintetizar las proteínas usando el antes mencionado código genético. Por estas razones se decidió utilizar las secuencias de ADN para su almacenamiento y compresión, a pesar de que contienen información aparentemente inútil.
2.1.2. Estructura del ADN Ya se ha dicho arriba que el ADN estaba formado por una sucesioón de bases nitrogenadas. Estas bases son cuatro que, por comodidad, se representan por su inicial: Adenina Citosina Guanina Timina
2.2. ÁRBOLES DE FILOGENIA
17
La molécula de ADN tiene una estructura de doble secuencia de bases complementarias. Dado que los emparejamientos están pre jados, sólo es necesario almacenar una de ellas para conocer la otra. La longitud de estas moléculas puede oscilar desde unos centenares a millones de bases. Cabe decir que los estudios en esta rama de la ciencia están en pleno desarrollo lo que impide en estos momentos otorgar signi cado alguno a las distintas combinaciones de bases de forma que pudiera repercutir en los métodos utilizados durante la compresión. Por este motivo se decidió que el algoritmo de compresión no debería hacer distinciones entre las distintas subcadenas de ADN.
2.2. Árboles de logenia Según la teoría de la evolución de las especies de Charles Darwin, todos los seres vivos son la evolución de un antepasado común. Un árbol de logenia es un grafo conexo acíclico en el que cada nodo representa a un organismo y cada arco
b
representa la relación de descendencia o evolución, de forma que se puede establecer qué seres tienen el antecesor común más cercano. Podríamos considerar el árbol genealógico de una familia como un árbol de logenia aunque los que se tratan en la realidad son más genéricos y, en lugar de tratar con individuos, tratan con especies. Sin embargo, un ejemplo con un b árbol genealógico servirá para explicar el uso y la construcción de estas estructuras.
Primo
Prima
Hermana
Individuo
Figura 2.2: Ejemplo de árbol de logenia de cuatro individuos
La gura 2.2 es el árbol logénico para cuatro individuos. Se aprecia cómo se crea el árbol de ancestros lógico según los parentescos dispuestos. Cabe resaltar que se crean nuevos individuos en un principio imaginarios que son ancestros de los reales o de otros creados de esta forma. Las conclusiones que se pueden extraer es que primo es más cercano a prima que al resto y lo mismo podemos decir de hermana e individuo. En este ejemplo, los nodos creados por el algoritmo corresponderían al abuelo, al padre y al tío del individuo.
2. CONCEPTOS PREVIOS
18
La complejidad de su construcción reside en decidir qué datos de cada individuo se usan para el estudio y en extraer información que sirva para construir el árbol a partir de los datos de cada individuo. Por supuesto, en este proyecto sólo nos interesan los obtenidos a partir de las secuencias de ADN mitocondrial de los distintos individuos. Este tipo de ADN, el mitocondrial, es algo especial puesto que sólo aparece en las mitocondrias, que son unos orgánulos presentes en las células de los organismos pluricelulares que realizan la respiración celular. Son los encargados de transformar el oxígeno en energía. La información genética almacenada es realmente extraña puesto que no sufre alteraciones durante la reproducción sino que es transmitida de forma directa a través del óvulo materno. De esta forma las variaciones sufridas a lo largo del tiempo son mucho menores que el resto de las cadenas de ADN, aunque estudios muy recientes apuntan cada vez más hacia la gran relevancia de dichas variaciones [15].
3 Desarrollo del estudio En este apartado se re eja el proceso de estudio de los distintos compresores de secuencias biológicas que han sido investigados, desde simples adaptaciones de algoritmos de compresión de carácter general a otros ya creados especí camente para secuencias de ADN.
3.1. Adaptación del algoritmo de Lempel-Ziv La primera opción como algoritmo de compresión para secuencias biológicas que sugirió la directora del proyecto fue la adaptación de los algoritmos de Lempel-Ziv al alfabeto formado por las cuatro bases nitrogenadas {A, C, G, T}. Generalmente, los algoritmos implementados de este tipo trabajan con bits o bytes, de forma que había que introducir alguna pequeña variación para que funcionaran con las secuencias de ADN. De entre la gran variedad de algoritmos de la familia LZ se eligió el LZ77 porque ofrecía la máxima simplicidad sin pérdida de capacidades. Este algoritmo recorre la entrada buscando en la parte aún no procesada una cadena que también esté en la parte ya recorrida, tal y como se explica en [20]. En caso de encontrar una repetición su cientemente larga, escribe una referencia a ella en lugar de la propia subcadena. Si no se encuentra tal repetición, se escribe el primer símbolo aún no procesado directamente en la salida y se continua con el siguiente símbolo hasta terminar el chero. La búsqueda puede limitarse hasta cierta ventana de comparación o comprobar todo el chero. Si está limitada en un cierto rango, la escritura de la referencia es más sencilla puesto que sólo pueden escribirse cierto rango de valores, lo que se puede hacer con un número de bits jo. Sin embargo, al limitar la búsqueda disminuye la probabilidad de encontrar una repetición y como consecuencia, la capacidad de compresión, por esta razón se eligió un algoritmo que hiciera una búsqueda completa. Por tanto, las referencias tuvieron que escribirse usando una
19
3. DESARROLLO DEL ESTUDIO
20
codi cación de longitud variable [1]. En todos los casos se exigía que una repetición tuviera una longitud mínima tal que escribir una referencia a ella ahorra espacio en comparación a escribirla de forma directa. Esta parte sufrió la mayor variación junto con la codi cación de los símbolos puesto que sólo se necesitan dos bits para codi car cualquiera de las cuatro bases nitrogenadas.
3.1.1. Resultados Los resultados obtenidos mediante esta adaptación no son en general buenos puesto que no se alcanzan niveles de compresión signi cativos. Usando como unidad el número de bits que necesita una base para ser escrita, el mejor de estos algoritmos conseguía alcanzar una ratio de 1.927. Teniendo en cuenta que sin utilizar ningún método de compresión, al ser únicamente cuatro elementos los que componen las secuencias de ADN, se puede alcanzar unos niveles de compresión de 2 bits por base, el resultado no es muy bueno. De hecho, si se considera que el coste en tiempo de las búsquedas era bastante grande, no merecía la pena usar el algortimo implementado frente a la codi cación directa de las bases.
3.2. Análisis de los algoritmos de compresión especí cos Al quedar patente que con la adaptación del algoritmo de Lempel-Ziv no se alcanzaban resultados muy buenos se decidió analizar en profundidad los algoritmos creados para la compresión de secuencias de ADN. No resultó di cil encontrar el que parecía dar mejores resultados, DNACompress [5]. Es el último de los algoritmos conseguidos por un mismo grupo de trabajo que también fue el responsable del GenCompress [4].
3.2.1. GenCompress Este algoritmo es muy similar al algoritmo de Lempel-Ziv presentado arriba. También recorre secuencialmente el chero buscando repeticiones en la parte que ya ha sido analizada. La diferencia clave es que introduce la capacidad de detectar repeticiones inexactas. Al parecer, las secuencias de ADN, al estar sujetas a mutaciones puntuales, pueden poseer repeticiones de bastante longitud en las que unos pocos elementos di eren entre ambas apariciones. Al introducir esta posibilidad la forma de referenciar repeticiones cambia pues debe adaptarse a las nuevas capacidades. Ésto se traduce en que una referencia inexacta se codi ca como una referencia exacta más una serie de operaciones de
3.2. ANÁLISIS DE LOS ALGORITMOS DE COMPRESIÓN ESPECÍFICOS 21 edición (inserción, sustitución y borrado) que afectan a algunos de los elementos de esa repetición. La forma en que decide si una repetición debe tenerse en cuenta o no depende ahora de más factores. Para simpli car, se asignan puntos positivos por cada elemento repetido y negativos en caso de elementos diferentes. Esta puntuación se calcula en función del coste de la codi cación de la cadena de operaciones que generaría. Cuando la puntuación de una repetición baja por debajo de un umbral se considera que no aportará más compresión si se continua con la misma referencia así que se decide acabar allí la repetición. La idea de aceptar repeticiones inexactas es innovadora pero los resultados empíricos no nos convencían mucho. En general, los elementos diferentes de las repeticiones aparecen al nal de las repeticiones puesto que son estos los que hacen bajar la puntuación hasta el límite permitido. Por esta razón no se consideró tan importante la capacidad de incluir repeticiones inexactas, al menos consideradas de esta forma.
3.2.2. Pattern Hunter La siguiente propuesta de este grupo de trabajo proponía un cambio radical. El compresor DNACompress se basa en los resultados de un motor de búsqueda de repeticiones llamado Pattern Hunter [8]. Este programa independiente devuelve una lista de las repeticiones inexactas más largas que tienen en común dos o más secuencias de ADN. DNACompress utiliza las salida producida por Pattern Hunter al ejecutarlo con un mismo chero como entrada para comprimir dicho chero cogiendo las mejores repeticiones. El algoritmo que nos interesa es el de Pattern Hunter. La diferencia principal con su predecesor es que trata la entrada de una manera totalmente distinta. Lo primero que hace es sacar una cadena binaria de comparación elemento a elemento de las entradas en las que un 1 indica que los elementos son iguales y un 0 indica que son distintos. Podemos ver un ejemplo en la gura 3.1. Secuencia A Secuencia B Diferencia
aaaccccaagggt aagctcaaagcgg 1101010111010
Cuadro 3.1: Ejemplo de construcción de cadena binaria
Cuando la entrada es una única cadena la compara con una copia desplazada de forma que todas las posiciones sean comparadas. Para buscar las repeticiones simplemente tendría que buscar secuencias de unos en la cadena binaria obtenida
3. DESARROLLO DEL ESTUDIO
22
pero como también permite repeticiones inexactas, lo que hace es buscar apariciones de un determinado patrón jo de longitud corta de forma que no require que todos los elementos sean unos. Por ejemplo, podría buscar en esa cadena binaria el patrón 11011 que indica que busque repeticiones inexactas que tengan dos bases repetidas alrededor de cada bases diferente. Una vez encontrados los patrones los intenta extender hacia ambos lados para obtener la mayor longitud posible. De nuevo, para considerar si un repetición es aceptable o no, utiliza el sistema de puntuación que también usa la versión anterior. Los resultados avalan este método fundamentalmente en lo que a velocidad se re ere puesto que al usar cadenas binarias las comparaciones se pueden agilizar. Sin embargo mantiene el problema de su predecesor de dejar las inexactitudes en las repeticiones cercanas a ambos extremos de la cadena.
3.2.3. Pattern Hunter II La última versión del compresor DNACompress [7] consiste únicamente en la modi cación del motor de búsqueda de repeticiones. Básicamente se trata de ampliar la posibilidad de encontrar repeticiones inexactas utilizando más de un patrón sobre la cadena binaria lo que hace que sea un algoritmo más exhaustivo que su primera versión sin aumentar drásticamente el tiempo de ejecución. Se presenta pues un nuevo problema muy complejo consistente en seleccionar un conjunto de patrones que funcionen de la mejor forma posible. Los resutados de esta nueva versión son muy similares a los de la primera versión aunque aumenta ligeramente la cantidad de repeticiones encontradas, lo cual mejora la compresión obtenida. El problema de estos dos algoritmos, claramente los mejores, es que no hay información su ciente para estudiarlos en profundidad y mejorarlos sin tener que usar ingeniería inversa a partir del producto nal para reconstruirlos. Esta razón hacía imposible su uso como base para implementar alguna mejora.
3.2.4. dnaX A pesar de los buenos resultados de los algoritmos Pattern Hunter, no resultaba muy satisfactoria la solución basada en las repeticiones inexactas puesto que, analizando los resultados, los elementos distintos aparecen de forma muy escasa (nunca más de tres en una repetición) y generalmente situados hacia los extremos de las secuencias repetidas. Se consideró posible alcanzar los mismos niveles de compresión sin necesidad de tener en cuenta las repeticiones inexactas simplemente acortando las repeticiones. El algoritmo dnaX [10] opta por esta solución y añade una característica nueva como es la búsqueda de repeticiones invertidas. Al consultar ésto con bioquímicos
3.2. ANÁLISIS DE LOS ALGORITMOS DE COMPRESIÓN ESPECÍFICOS 23 se descubrió que no era descabellado encontrar inversiones de trozos de secuencias de longitudes que pueden llegar a casi un millón de bases [18]. Este algoritmo funciona de una forma algo distinta que los vistos con anterioridad. Básicamente trocea la secuencias en fragmentos de 20 bases y, tras la búsqueda de repeticiones exactas, codi ca la entrada según estos bloques, diciendo qué partes de las 20 bases están ya repetidas y qué partes no, referenciando las primeras y escribiendo las últimas directamente en el chero de salida. Las referencias a repeticiones deben ahora llevar un bit que indique si son repeticiones directas o inversas. Según el artículo que lo describe, los resultados que presenta este algoritmo son similares a los del Pattern Hunter tanto en tiempo como en tasa de compresión. Además, el autor facilitó las fuentes del algoritmo lo que hacía mucho más fácil el trabajo partiendo de su código para introducir alguna mejora.
24
3. DESARROLLO DEL ESTUDIO
4 Implementación del compresor En esta sección describo la solución implementada como compresor de secuencias de ADN. En la sección 6 se describen los resultados obtenidos con nuestro compresor y en comparación con los ya existentes.
4.1. Especi cación del algoritmo Algoritmo: Entrada:
Compresor de cheros de ADN
Fichero en el que únicamente aparezcan los caracteres A, C, G y T en
mayúsculas o minúsculas.
Salida:
Se crea un chero que ocupa menos espacio que la entrada y que contiene
la misma información, de forma que se pueda recuperar el original utilizando un descompresor.
4.2. Directivas de diseño Tras el estudio realizado al problema se han obtenido ciertos elementos de diseño que se considera que el algoritmo debe tener presentes. Éstos se re eren tanto a las características particulares del tipo de datos tratado como al uso que se le va a dar a la aplicación obtenida.
4.2.1. Sobre los datos Las secuencias de ADN están formadas por cuatro elementos, por tanto con 2 bits por cada base se puede escribir el chero. Cualquier archivo comprimido generado debería superar esta tasa de compresión.
25
4. IMPLEMENTACIÓN DEL COMPRESOR
26
La longitud de las secuencias de ADN es enormemente diversa, desde unos pocos cientos a varios millones de bases. No se conoce ninguna estructura común a todas las secuencias de ADN su cientemente de nida que permita dividirlo en secciones por razones semánticas o funcionales. La frecuencia de las distintas bases nitrogenadas es, en general, igual para todas ellas. El ADN suele contener repeticiones de longitudes muy variadas que no tienen por qué seguir cierta localidad espacial. Debido a la posibilidad biológica del ADN de sufrir mutaciones puntuales pueden aparecer repeticiones de secuencias no exactas que se diferencian en unas pocas bases. En las secuencias de ADN pueden aparecer fenómenos de inversión de ciertas subcadenas.
4.2.2. Sobre el uso del algoritmo Las condiciones de uso del algoritmo son de vital importancia para tenerlas en cuenta al diseñarlo. En el caso que nos ocupa el proceso de trabajo con una secuencia de ADN es aproximadamente el siguiente. 1. Se extrae en el laboratorio la molécula de ADN que se desea obtener. 2. Se secuencializa, también por métodos químicos, la molécula extrayendo así la sucesión de bases nitrogenadas. 3. Se introduce la secuencia obtenida en una base de datos de ADN. 4. Se consulta todas las veces que se necesite para compararla con otras muestras obtenidas o para cualquier otro cometido. Se puede deducir que la operación que más se realiza con este tipo de datos es la de consulta lo que nos sugiere que es ésta operación la que hay que agilizar en mayor medida, pudiendo invertir más tiempo en otras operaciones.
4.3. Estructura del algoritmo El algoritmo se divide en tres fases diferenciadas para facilitar su comprensión y su mantenimiento y son el análisis de la entrada, la selección de las repeticiones y la codi cación, como se ve en la gura 4.1.
4.3. ESTRUCTURA DEL ALGORITMO
Entrada
An´alisis
Selecci´on
27
Codificaci´on
Salida
Figura 4.1: Fases del algoritmo
4.3.1. Análisis de la entrada En esta fase se trata de extraer la máxima información de la entrada que pueda servir posteriormente para comprimir al máximo. Fundamentalmente lo que se buscan son repeticiones dentro del chero de forma que luego puedan sustituirse las subsecuencias por referencias a otras que son iguales. La búsqueda de las repeticiones en el chero es una de las partes más costosas del algoritmo y donde hay que re nar mucho el código para optimizar todo lo que se pueda el tiempo de ejecución. Sin embargo hay que tener en cuenta lo comentado anteriormente del proceso de trabajo con una secuencia de ADN en la que la compresión únicamente se realizaría una vez antes de almacenarla en la base de datos por lo que puede ser relativamente lenta comparado con la descompresión. Dado que la velocidad del algoritmo no era una prioridad se implementó como primera versión una busqueda exahustiva simple en la que para cada posición se buscaba en todo el chero la repetición más larga. Este código, aunque e caz, era ya intratable para cheros de unos pocos millares de bases pues hacía enormemente costoso realizar cualquier prueba. La segunda opción surgió a partir de lo leído en [3] que indicaba que los árboles de su jos eran un tipo de datos que se amoldaba muy bien a la tarea a realizar. La di cultad de implementación de las operaciones sobre estas estructuras hizo que se optara por una versión más sencilla aunque un poco más ine ciente, los vectores de su jos [9, 17]. Los vectores de su jos se basan en la ordenación de los su jos de una cadena de forma que se pueden encontrar las subcadenas repetidas como los pre jos comunes de dos su jos consecutivos en la lista ordenada. Esta solución era satisfactoria en velocidad pero presentó un problema en la fase de selección de repeticiones. En caso de que dos subcadenas repetidas estén solapadas o varias repeticiones se re eran a una misma sección de la secuencia se debía descartar su uso y no se podían utilizar ni siquiera parcialmente para otra posible repetición. Debido a estos problemas se volvió a intentar la solución basada en los árboles de su jos porque permitían salvar los fallos de la anterior propuesta. Siguiendo las explicaciónes de Ukkonen [19] se implementó esta solución. Sin embargo no resultó la de nitiva por varios motivos. El primero es que no había una forma sencilla de ampliar los árboles de su jos para que permitieran encontrar repeticiones invertidas y el segundo fue que era muy costoso encontrar las repeticiones porque aunque
4. IMPLEMENTACIÓN DEL COMPRESOR
28
la búsqueda de una subacadena es muy rápida, el número de subcadenas de una secuencia es muy grande como para que sea su cientemente rápido buscar todas y coger las mejores. A pesar de esto, la visión que Ukkonen da a los árboles de su jos tratándolos como autómatas sugirió la posibilidad de usar algún autómata para este trabajo. Precisamente ésto es lo que se describe en [14], donde se usan los autómatas para encontrar todas las repeticiones de subsecuencias en una secuencia. El funcionamiento además es simple y curioso. Basta con construir un autómata nito no determinista capaz de reconocer todas las subcadenas de una cadena de ADN y luego, al aplicarle la tranformación que lo convierte en determinista, se puede recuperar la información correspondiente a las repeticiones encontradas. Su sencillez permite a la vez extender el algoritmo descrito en el artículo para encontrar también las repeticiones invertidas simplemente modi cando el autómata para que reconociera las subcadenas invertidas de la secuencia.
4.3.2. Selección de las repeticiones Esta segunda fase recoge las repeticiones encontradas en la primera y selecciona las que mayor tasa de compresión permiten. La compresión que aporta una repetición se puede cuanti car teniendo en cuenta lo que cuesta codi car las bases sin referenciar y lo que constaría crear la referencia. Una referencia consta de cinco elementos:
Original
Posición de la primera aparición
Repeticion Longitud Tipo
Posición de la segunda aparición
Longitud
Es directa o invertida
Los tres primeros son enteros positivos y el último un booleano. No se puede saber a priori la magnitud de los enteros puesto que no conocemos las posiciones relativas de las repeticiones y no hay ninguna longitud predilecta. Sin embargo, para tener en consideración la aparición de posibles mutaciones puntuales, una vez ordenadas las repeticiones por orden de posición dentro del chero, se puede suponer que dos repeticiones consecutivas están muy próximas y se puede almacenar la distancia entre ambas en lugar de la posición absoluta. La cuanti cación del bene cio de una referencia queda determinado por la siguiente fórmula:
Benef icio = Ref erencia − Codif icacin directa
4.3. ESTRUCTURA DEL ALGORITMO
29
Ref erencia = 3 × Entero + 1 Codif icacin directa = 2 × Longitud Además de seleccionar las repeticiones usando el bene cio como principal factor hay que tener en cuenta que no se referencien dos veces la misma zona del chero por lo que hay que controlar que las repeticiones no se solapen. Si tenemos en cuenta el algoritmo de descompresión se puede apurar aún más el uso de las repeticiones. La reconstrucción se realiza en orden secuencial de forma que no es necesario tener toda la referencia completa antes de escribir el trozo repetido. Se pueden utilizar repeticiones solapadas. Un ejemplo de un caso extremo pero muy clari cador es el siguiente: Secuencia:
aaaaaaaa
Si consideramos las repeticiones que no se solapen nos podría quedar un chero comprimido con la siguiente información:
aaaa, (0, 4, 4, normal) El paréntesis corresponde a la repetición que comienza en la posición 4, es igual a la que empieza en la posición 0 de longitud 4 en el orden normal. Si consideramos las repeticiones solapadas, esta misma secuencia podría quedar de la siguiente forma:
a, (0, 1, 7, normal) Vemos que ahora la repetición comienza en la posición 1 y que es igual a la que empieza en la posición 0 de longitud 7 en sentido normal. Esto es posible porque en cuanto se escribe la primera a repetida se incorpora a la cadena, lo que servirá a su vez para reconstruir el resto. Esta posibilidad no se presenta cuado las repeticiones están invertidas porque se necesita el último elemento de la subsecuencia original para recuperar la primera base de la repetida. Así que a la hora de seleccionar las secuencias que se usarán en las referencias, las repeticiones directas son mejores.
4.3.3. Codi cación de la salida Ésta es la última fase del proceso pero puede intervenir en algunos aspectos del resto de las fases, fundamentalmente en el cálculo de los bene cios que se obtienen al considerar una repetición. La compresión obtenida depende del método de codi cación empleado para escribir los enteros y también del que se usa para las bases.
Codi cación de los enteros Es uno de los puntos en los que más se ha trabajado para intentar reducir el tamaño de la codi cación. El problema se reduce a escribir en el mínimo espacio un conjunto de enteros de los que se sabe bastante poco.
4. IMPLEMENTACIÓN DEL COMPRESOR
30
Lo primero que se desconoce es un rango su cientemente preciso. Es cierto que se puede hacer una estimación considerando que todos los enteros serán positivos y, como mucho, de la longitud de la secuencia. Sin embargo, esta estimación es muy mala puesto que los enteros más grandes son menos probables y una representación de longitud ja llevaría a un desperdicio de espacio. Hay que utilizar pues una codi cación de enteros de longitud variable. Este tipo de codi caciones puede llegar a ser muy complejo, como las basadas en los números de Fibonacci o en la rampa logarítmica, y esta complejidad se traduce en tiempo de cómputo que ralentiza la ejecuión en gran medida. Una solución sencilla y e ciente es la que se utiliza en el algoritmo dnaX [10] llamada Codi cación de Bit de Continuidad (CBC). Se basa en dividir la codi cación binaria del entero en grupos de bits de tamaño jo e intercalar entre estos un bit que será un 0 entre los dos últimos grupos y un 1 en el resto. Se puede ver un ejemplo en el cuadro 4.1, donde se utiliza éste método formando grupos de tres bits y añadiendo el de continuidad.
Decimal
Binario
CBC
75
1001011
1001 1001 0011
Cuadro 4.1: Codi cación de Bit de Continuidad
Aparte del método de codi cación, se puede variar el dato en sí para hacerlo más pequeño. Esto es algo que hemos aplicado puesto que en lugar de escribir las posiciones de las repeticiones se escriben las diferencias con las posiciones de las repeticiones anteriores, de forma que escribir la resta entre dos enteros es siempre más económico que escribir cualquiera de ellos. Lo único que permacece sin especi car de manera ja es el tamaño de los grupos que se utilizan en la codi cación de bit de continuidad. Éste es un parámetro que hay que jar de forma empírica y cuyo valor óptimo puede variar para cada chero de ADN.
Codi cación de las bases Se sabe que las bases se pueden codi car utilizando 2 bits para cada una. La cuestión es si este límite se puede reducir. Para ello se han probado métodos estadísticos de compresión como pueden ser los códigos de Human, arítmetico o de rango descritos en [2, 11, 13]. El primero se muestra incapaz de bajar del límite puesto que las diferencias entre las frecuencias de las bases son mínimas. Los otros dos son de la misma familia y sí que consiguen en algunos casos reducir la codi cación. El aritmético posee ciertas trabas por licencias así que se empleó el de rango para este proyecto.
4.4. CONSIDERACIONES GENERALES
31
El problema que presenta en la práctica es que en ocasiones supera el límite de 2 bits por base y realiza una codi cación peor. Por eso es necesaria una comprobación y, en caso de detectar que no consigue la compresión, se utiliza la traducción directa a dos bits.
4.4. Consideraciones generales Además de las directivas de diseño que se desprendían de los estudios de otros algoritmos ya existentes, se han tomado otras decisiones para incrementar las prestaciones del algoritmo desarrollado. En cuanto a la mejora en velocidad se ha optado por limitar ciertos elementos para que se redujera el tiempo de cáculo. En este apartado cabría destacar la acotación de la búsqueda de repeticiones a las que que sean más largas que una cierta longitud mínima. Este límite inferior viene marcado por la fórmula de beni cio, ya que no se aceptan las repeticiones que no aportan bene cio. Para ello se calcula para cada chero cuál es la longitud mínima de las repeticiones en el mejor de los casos, es decir, con los demás datos de la referencia lo más pequeños posibles. En el caso de la organización del chero comprimido se contrastaron dos versiones distintas. En una, las referencias se almacenan separadas del resto de los elementos no referenciados. La otra opta por insertar una marca entre las bases no referenciadas que indique que allí hay una referencia. Esta segunda forma permite eliminar uno de los campos de las referencias sin embargo añade un nuevo símbolo al alfabeto lo que hace que 2 bits no sean su cientes para representarlos. Las pruebas demostraron que la primera opción era la que más comprimía. Otro aspecto fundamental que se deseaba evitar era la parametrización. Gran parte de los algoritmos estudiados permitían variar ciertos parámetros para incrementar la compresión. Éstos parámetros no son intuitivos ni tienen relación directa con aspectos apreciables en la cadena de adn, de forma que cualquier usuario sería incapaz de decidir sin realizar varias pruebas cuál es el valor óptimo para cada parámetro. Dado que la compresión de una secuencia de ADN es una operación que se repite con poca frecuencia, se propuso que la elección del mejor valor la hiciera el propio algoritmo. Un ejemplo de este comportamiento es la búsqueda de la longitud mínima para las repeticiones, algo que otros algoritmos jaban de forma estática.
4.5. Interfaz grá ca La última tarea que se realizó en la fase de implementación del compresor fue dotarlo de una interfaz grá ca que facilitara la extracción de los resultados y la
4. IMPLEMENTACIÓN DEL COMPRESOR
32
comparación entre los distintos algoritmos.
Figura 4.2: Ventana principal Fundamentalmente consta de una ventana principal que nos muestra dos cuadros de selección donde se elige tanto el algoritmo que se va a usar como la acción (compresión o descompresión). También están los dos campos fundamentales correspondientes a los cheros de entrada y salida del algoritmo. Por último, y en los casos que el algoritmo lo requiera, se puede especi car el valor de un parámetro que interviene en la codi cación de los enteros. Por supuesto aparecen también los botones necesarios para que comience la acción elegida y el que provca que se acabe la ejecución del programa. Una imagen de esta ventana se puede ver en la gura 4.2.
Figura 4.3: Ventanas de estadísticas Una vez concluida la ejecución de uno de los dos compresores, se muestra por pantalla en otra ventana la información del chero que se ha comprimido y la
4.5. INTERFAZ GRÁFICA
33
tasa de compresión que se ha alcanzado (en bits por base). Ésto permite realizar las pruebas de una forma sencilla y rápida. Se pueden ver unos ejemplo de estas ventanas en la gura 4.3.
34
4. IMPLEMENTACIÓN DEL COMPRESOR
5 Árboles logénicos En esta sección se tratan las características que debe tener un compresor de secuencias biológicas para poder ser usado como herramienta en la construcción de los árboles de logenia. Ya se ha comentado en secciones anteriores que los árboles logénicos tienen como nalidad crear una estructura grá ca que represente las relaciones evolutivas de distintos individuos. En el caso de las secuencias biológicas, siven para conocer las ramas evolutivas que han llevado a la existencia de las distintas especies según la teoría de Darwin. Todos los métodos que existen se podrían clasi car en dos grandes grupos dependiendo de cómo comparan las secuencias. El primer grupo utiliza toda la información de todas las secuencias para construir el árbol. El segundo, compara las secuencias dos a dos y obtiene una matriz numérica simétrica cuyos valores caracterizan la similitud entre las dos secuencias. La intención del proyecto es la de utilizar el compresor como herramienta para generar el árbol así que se aprovechan las comparaciones que realiza el propio algoritmo descrito en la sección 4 para contabilizar la similitud entre dos secuencias. De esta forma, se construye una matriz de valores que luego servirá para generar el árbol.
5.1. Cálculo de la distancia entre dos secuencias En el artículo [4] realizan una tarea similar aunque con pretensiones más teóricas, pues tratan de caracterizar la complejidad de Kolmogorov de una cadena tanto simple como condicionada a otra y usar los resultados existentes sobre este tema para conseguir un número que indique la similitud entre dos secuencias de ADN. La medida que se usa en el proyecto como distancia entre dos secuencias es
35
5. ÁRBOLES FILOGÉNICOS
36
básicamente la tasa de compresión que se alcanza al comprimir la concatenación de esas dos secuencias. Este método no asegura que la matriz sea simétrica pero experimentalmente se comprueba que la variación es practicamente nula entre las dos posibles permutaciones del par de secuencias. De todas formas, se ha considerado directamente la media de las tasas de las dos permutaciones como distancia entre la pareja de secuencias, lo cual asegura la simetría.
5.2. Características del compresor Con estos planteamientos ya se pueden extraer algunas conclusiones de cómo debería ser el algoritmo de compresión para considerarlo como correcto en el cáculo de la similitud. Entre otras cosas, debe tener capacidad de almacenamiento de la parte de la secuencia ya procesada porque al tratar la parte correspondiente al segundo individuo, debe poder reconocer esos mismos elementos en la parte correspondiente al primero. Con este requerimiento se eliminan los compresores estadísticos como podrían ser los códigos de Human o la codi cación aritmética. Dentro de la familia de los algoritmos de Lempel-Ziv se deben excluir los que derivan del LZ78 porque el método que utiliza para crear el diccionario de las subsecuencias encontradas es muy inestable. Con esto me re ero a que la variación 1
de una única base puede provocar la reconstrucción de todo el diccionario . Por esa razón sólo se pueden considerar útiles aquellos algoritmos que almacenan las secuencias de una forma más consistente. En este grupo se incluyen por supuesto el DNACompress y el dnaX que, al ser especí cos de las secuencias de ADN, recogen mejor las similitudes que los no dedicados como el gzip.
5.3. Métodos de cálculo En este punto ya se dispone de una matriz de valores con las distancias entre los distintos individuos. Se presentan de nuevo multitud de métodos para conseguir la forma arbórea del esquema. El más simple, busca la pareja más cercana, genera un individuo imaginario antecesor de ambas secuencias recalculando las distancias con el resto y repite el proceso hasta construir el árbol. En el otro extremo están los que consideran todos los posibles árboles y se quedan con el más probable basándose en el mínimo cambio entre padre e hijo u otras leyes de evolución. La elección del método de cálculo no es sencilla a priori puesto que la información que se maneja ya no es de tipo biológico sino matrices de números de las que
1 Es
un ejemplo de la catástrofe del bit [13, 12]
5.4. HERRAMIENTAS UTILIZADAS
37
poca información se puede extraer. Por eso se tomó la decisión de utilizar varias alternativas y escoger la que mejores resultados diera.
5.4. Herramientas utilizadas Como ya he dicho en la anterior sección, los métodos de construcción de árboles a partir de matrices numéricas están muy desarrollados por lo que se optó por usar algún paquete de software ya desarrollado. Se encontró de esta forma el 2
paquete PHYLIP
del Departameto de Biología de la Universidad de Washington,
que ofrece los algoritmos que se estaban buscando y otros que permiten la construcción grá ca del árbol logénico. Los métodos que incorpora este paquete son los siguientes: Fitch Kitch Neighbor El primero y el segundo calculan la logenia a partir de la matriz de distancias usando el modelo que estima que las distancias deben igualar las sumas de las longitudes de las ramas de las distintas especies. Utilizan ambas el criterio de Fitch-Margoliash. La diferencia fundamental es que el método Kitch asume un reloj evolutivo lo que se traduce en que las longitudes totales de las ramas (desde la raiz a las hojas) deben ser iguales, pues son estas longitudes las que representan el tiempo. El método Fitch no considera esta restricción por lo que no se puede hacer ningún cálculo temporal sobre los resultados. El tercer método es el más simple de todos aunque también el más rápido y construye el árbol uniendo los
linages
más parecidos hasta llegar a unir todos. Por su simplicidad no considera
tampoco reloj evolutivo por lo que no se pueden realizar cálculos temporales sobre sus resultados. Las pruebas realizadas para comprobar qué método se ajustaba mejor a la construcción de árboles basados en cadenas de ADN y los resultados obtenidos se explican en detalle en la sección 6 de Resultados.
2 http://evolution.genetics.washington.edu/phylip.html
38
5. ÁRBOLES FILOGÉNICOS
6 Resultados En esta sección se comentan las pruebas realizadas con el compresor y con los métodos de construcción de árboles de logenia.
6.1. Resultados del compresor En esta parte se especi can las pruebas realizadas al compresor y se expone una comparativa con los otros algoritmos de referencia utilizados.
6.1.1. Banco de pruebas Las pruebas se han realizado en primer lugar sobre un banco de pruebas que es usado en todos los artículos que se han consultado. No se explica en ninguno de ellos la razón de su uso pero parece muy estandarizado. Los resultados sobre este banco de pruebas se pueden consultar en el cuadro 6.1. El tamaño está medido en número de bases y el nivel de compresión indicado en cada casilla se re ere a los bits por base que ocupa el chero obtenido. Se puede comprobar que el algoritmo dnaX es mejor que el resto en prácticamente todos los cheros. Al comprobar estos resultados y volver sobre el artículo que de ne este algoritmo [10], se sospechó que el algoritmo estaba hecho prácticamente a la medida de este banco de pruebas así que se decidió construir otro banco de pruebas independiente para comprobar si mantenía el mismo rendimiento. El segundo banco de pruebas (Cuadro 6.2), se construyó cogiendo una secuencia genética de cada una de las clases en que las divide la base de datos NCBI buscando a la vez diversidad en las longitudes de las secuencias.
1 http://www.ncbi.nlm.nih.gov/
39
1
6. RESULTADOS
40
Secuencia Tamaño dnaX DNACompress Mi Algoritmo chmpxx 121024 1.68 1.84 1.96 chntxx 155844 1.62 1.93 2.00 hehcmvcg 229354 1.85 1.97 2.00 humdystrop 38770 1.95 1.92 1.99 humghcsa 66495 1.38 1.93 1.32 humhprtb 56737 1.92 1.92 1.97 mpomtcg 186608 1.93 1.96 1.97 vaccg 191737 1.76 1.91 1.93 Cuadro 6.1: Banco de pruebas ajeno
Secuencia Tamaño dnaX DNACompress Mi Algoritmo Aeromonas 11822 2.05 1.96 2.00 Anisakis 13916 1.84 1.77 1.85 Citrus Dwarf 294 3.95 2.37 2.12 Deinococcus 412344 1.87 1.88 1.98 Methanohalophilus 2158 2.44 1.89 2.02 Nanoarchaeum 490885 1.85 1.86 1.98 Plasmodium 643292 1.59 1.67 1.68 Porphyra Pluchra 6427 2.11 1.95 1.98 Virus de la Rabia 11932 2.07 1.97 2.00 Salmonella 46900 2.00 1.98 2.00 Cuadro 6.2: Banco de pruebas propio
6.1.2. Análisis de los resultados El análisis realizado a los datos tenía como objetivos fundamentales dos aspectos sobre los algoritmos:
Comparar los niveles de compresión de los distintos algoritmos.
Averiguar si la e ciencia de los algoritmos era similar en los distintos bancos de pruebas.
Para conseguir estos objetivos se recurrió a realizar un estudio estadístico de los resultados.
6.1. RESULTADOS DEL COMPRESOR
41
Elección del estadístico Este es un punto fundamental a la hora de realizar el análisis pues afecta a todo el proceso. Se presenta una duda entre dos opciones al elegir el estadístico más correcto. La primera opción es la más simple y utiliza como elemento de medida la tasa de compresión (bits/base) obtenida en cada ejecución del algoritmo. Parece ser la más sencilla e intuitiva pero hay casos en los que perjudica de forma excesiva a cierto algoritmo. Si se observan los datos correspondientes al
Citrus Dwarf
del Cuadro
6.2, destaca de forma contundente el resultado correspondiente al algoritmo dnaX, que obtiene una tasa de 3.95 cuando el límite superior permitido es de 2 bits por base. Sin embargo, dado que el tamaño de esa secuencia es muy pequeño, sólo 294 bases, esto representa una pérdida de apenas 574 bits, lo que representa una cantidad nimia si tenemos en cuenta la ganancia que se obtiene en otros cheros más grandes. La segunda opción recoge este caso de forma que se considera como medida de compresión la tasa de compresión de todos los cheros juntos, es decir, el total del tamaño comprimido dividido para el total de bases. De esta forma se diluye el nefasto resultado antes mencionado pues su ponderación en el resultado nal es prácticamente despreciable. Sin embargo esta segunda opción no re eja con exactitud todos los aspectos que intervienen en la compresión. Además de la obligatoria cabecera que se ha de introducir en los cheros comprimidos y que hace que las tasas de los cheros pequeños sean peores, la decisión de poner una longitud mínima ja para las repeticiones también in uye en la capacidad de compresión, perjudicando de nuevo a los cheros pequeños. Dado que este factor era uno de los tratados en la implementación realizada en este proyecto, parece fundamental que se vea re ejado en el análisis. Por eso se eligió la tasa de compresión de cada chero como estimador.
Comparativa de los niveles de compresión La cuestión que se aborda con este análisis es averiguar si el algoritmo implementado era igual, mejor o peor que los otros dos que se han tomado como referencia. Para conseguir ésto, la prueba más conveniente es una comparación de las medias de las tasas, basada en la t de Student, teniendo en cuenta que los resutados de ambos algoritmos provienen de los mismos datos, lo que es equivalente a decir que los datos están emparejados. Con los resultados presentados en el Cuadro 6.3 se puede a rmar que las medias son iguales para las dos muestras a un nivel de con anza de 95 %. Es decir, en media, tanto el algoritmo implementado como el basado en Pattern Hunter obtienen la misma tasa de compresión.
6. RESULTADOS
42
Media Varianza Observaciones Grados de libertad Estadístico t P(T0,
// T( n ) :
en
correspondientes
NSIMBOLOS
// PRE :
//
simbolos
cuatro
#define int int
y
ADN_H
los
//
adn
ADN_H
numero
∗ − ∗ − ∗/
de
1
0,
un
esta
asociado
variable entero
es
a
un
fichero
válido
y
el
y
el
válido
leido
en
longitud
variable
continuidad )
O( l o g
n)
getlvs () ;
// PRE : //
El
flujo
parámetro
// POST : //
// T( n ) :
bool
de
// POST : // T( n ) :
True
entrada longitud
n
un
esta
asociado
variable
entero
continuidad )
O( l o g
f a i l () {
// PRE :
de de
Devuelve
( bit
leido
y
es en
return
Devuelve
true
si
ha
currido
contador ;
flujo ;
BUFFER_SIZE =
8;
l ;
obstream { :
obstream ( ) ;
True Crea
// T( n ) :
O( 1 )
por
algún
O( 1 )
// POST :
fichero
un
un
flujo
de
bits
de
válido
variable bit
flujo . f a i l () ; } ;
:
// PRE :
un
longitud
precedido
buffer ;
ifstream
a
válido
n)
private char int static const int int
class public
a
O( 1 )
// f u n c i o n e s
};
variable
True
// POST :
int
de
close () ;
// PRE :
int
parametro
True
// POST :
int
el
O( 1 )
open (
// PRE :
void
61
salida
fallo
de
signo
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
62
int
obstream (
// PRE : // POST : //
k) ;
True Crea
en
// T( n ) :
flujo
de
bits
variable
de
salida
con
( continuation
parametro
bit
k
para
const char
∗ nombre ) ;
True
// POST :
Crea
// T( n ) :
O( 1 )
un
flujo
const char
obstream (
// PRE :
de
bits
∗ nombre ,
True
// POST :
Crea
un
flujo
//
con
//
( continuation
// T( n ) :
parametro
de
k
bit
int
bits
para
de
salida
asociado
al
fichero
nombre
asociado
al
fichero
nombre
k) ;
de
salida
lectura
en
longitud
variable
encoding )
O( 1 )
~obstream ( ) ;
// PRE :
True
// POST :
Cierra
el
flujo
//
libera
la
memoria
y
// T( n ) :
void
int
return
el
parametro
open (
el
parametro
const char
Asocia O( 1 )
a
k
de
longitud
variable
a
k
∗ nombre ) ;
el
flujo
el
buffer
de
salida
al
fichero
y
cierra
el
flujo
nombre
close () ;
// PRE :
True
// POST :
Vuelca
// T( n ) :
O( b u f f e r . s i z e )
de
salida
volcar () ;
// PRE :
True
// POST :
Vuelca
// T( n ) :
O( b u f f e r . s i z e )
// f u n c i o n e s El
// POST :
flujo
escribe
// T( n ) :
buffer
bit ) ;
de
salida
bit
en
el
esta
asociado
flujo
de
a
un
fichero
válido
un
fichero
válido ,
salida
O( 1 )
int
put (
// PRE :
bool
el
escritura
putbit (
// PRE :
//
variable
True
// T( n ) :
void
longitud
O( 1 )
// POST :
void
de
l ;};
devuelve
// T( n ) :
void
buffer ,
True
// POST :
void
el
O( 1 )
getK ( ) {
// PRE :
volcando
k) ;
Establece
// T( n ) :
void
salida ,
k > 0
// POST :
// PRE :
de
O( 1 )
setK (
// PRE :
int
lectura
encoding )
O( 1 )
obstream (
// PRE :
un
longitud
El
0 <
c ,
flujo
bits
<
// POST :
escribe
// T( n ) :
O( b i t s )
int
bits ) ;
de
salida
32 , c
en
esta
asociado
l o g 2 ( c ) = 0
salida
usando
usando
bits
A.5. ENTRADA-SALIDA DE BITS
void
putlv (
// PRE : //
El
el
// POST : // T( n ) :
void
int
//
en
el
de
n
int
de de
Escribe
El
// POST : // T( n ) :
un
es
salida
fichero
válido ,
n >= 0 ,
válido
usando
bit
de
continuidad
n) ;
flujo
O( l o g
flujo
variable
a
n)
entrada longitud
n
en
por
el un
esta
flujo bit
asociado
variable de
de
es
a
un
fichero
válido
y
el
válido
salida
usando
bit
de
continuidad
y
signo
n)
bool
put ( v e c t o r <
// PRE :
longitud
asociado
escribe
precedido
void
en
variable
El
// T( n ) :
n
esta
longitud
parámetro
//
salida de
O( l o g
// POST :
de
parametro
putlvs (
// PRE :
// e s c r i b e
n) ;
flujo
63
flujo
Escribe
de
las
> &v ) ;
entrada
esta
componentes
asociado del
a
vector
un v
fichero en
el
válido
flujo
de
salida
O( v . s i z e ( ) )
int private int int static const int int size ;
//
numero
de
bits
escritos
en
el
flujo
:
buffer ;
contador ;
ofstream
flujo ;
BUFFER_SIZE =
8;
l ;
};
#endif
A.5. Entrada-Salida de Bits /∗
∗ Fichero : bstream . cc ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ Contenido : Implementación de l a s c l a s e s de s t r e a m s a f i c h e r o s de ∗ entrada y s a l i d a ( ibstream y obstream r e s p e c t i v a m e n t e ) ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#include #include #include #include #include #include using namespace
" bstream . h"
std ;
ibstream : : ibstream () { buffer
=
contador l
=
0; =
0;
0;
}
ibstream : : ibstream ( buffer
=
0;
int
k){
bits
de
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
64
contador l
=
0;
= k;
}
ibstream : : ibstream ( buffer
=
contador
0; =
const char
∗ nombre ) {
0;
f l u j o . o p e n ( nombre ) ; l
=
0;
}
ibstream : : ibstream ( buffer
=
contador
0; =
const char
∗ nombre ,
int
0;
f l u j o . o p e n ( nombre ) ; l
= k;
}
ibstream : : ~ ibstream () { flujo . close () ; }
void l
i b s t r e a m : : setK (
= k;
int
k){
}
void
i b s t r e a m : : open (
buffer
=
contador
0; =
const char
∗ nombre ) {
0;
f l u j o . o p e n ( nombre ) ; }
void
ibstream : : c l o s e () {
flujo . close () ;
}
bool if
ibstream : : g e t b i t () {
if else
( contador
==
0) {
(! flujo . eof () )
buffer
=
f l u j o . get () ;
buffer
=
0;
contador
int
= BUFFER_SIZE ;
}
bit
buffer
return
contador
}
− 1) ;
=
b u f f e r >>(BUFFER_SIZE
arn : : arn ( ) { raiz
=
0;
}
arn : : ~ arn ( ) { borrar () ; }
std ;
conjuntos
A.7. ÁRBOLES ROJINEGROS
int if return
int return
arn : : buscar ( vector < ( c o n j u n t o . empty ( ) )
69
> &c o n j u n t o ) {
buscar ( conjunto ,
− 1;
0) ;
}
int
int
arn : : buscar ( vector <
∗ aux ;
nodo
if if return
aux
=
return
(p +
− 1;
1 == v . s i z e ( ) )
return
∗ arn : : buscarNodo ( ∗ aux = r a i z ;
while if if else
−>d a t o ;
aux
−>s i g u i e n t e −>b u s c a r ( v ,
aux
a r n : : nodo nodo
p){
buscarNodo ( v [ p ] ) ;
( ! aux )
}
int
> &v ,
c){
return
( aux ) {
aux
−>c l a v e == c ) −>c l a v e > c ) = aux−>i z q u i e r d o
aux
= aux
( aux
( aux
return
int
p+1) ;
aux ;
;
−>d e r e c h o ;
}
}
void if
0;
arn : : i n s e r t a r (
int
id ,
int
vector<
( ! c o n j u n t o . empty ( ) ) i n s e r t a r ( id ,
conjunto ,
> &c o n j u n t o ) {
0) ;
}
void if if else if
arn : : i n s e r t a r (
∗ aux
nodo
=
int
id ,
int
vector<
buscarNodo ( v [ p ] ) ;
> &v ,
int
p){
( ! aux )
aux
=
(p +
insertarNodo (v [ p ] ,
−1) ;
1 == v . s i z e ( ) )
−>d a t o
aux
=
id ;
{
new
−> s i g u i e n t e ) −> s i g u i e n t e = arn ; aux−>s i g u i e n t e −> i n s e r t a r ( i d ( ! aux
aux
,
v,
p +
1) ;
} }
int
∗ arn : : i n s e r t a r N o d o ( ∗x = insertarABB ( c , d ) ; ∗ nuevo = x ;
a r n : : nodo nodo nodo
while if if
−> c o l o r
x
=
c ,
int
d){
rojo ;
r a i z && x−>p a d r e −> c o l o r == r o j o ) { −>p a d r e == x−>p a d r e −>p a d r e −>i z q u i e r d o ) { n o d o ∗ y = x−>p a d r e −>p a d r e −>d e r e c h o ; ( y && y−> c o l o r == r o j o ) { x−>p a d r e −> c o l o r = n e g r o ; y−> c o l o r = n e g r o ; x−>p a d r e −>p a d r e −> c o l o r = r o j o ; x = x−>p a d r e −>p a d r e ; (x
!=
(x
else if
}
{
−>p a d r e −>d e r e c h o ) { −>p a d r e ;
( x == x x = x
rota_i ( x) ; }
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
70
−>p a d r e −> c o l o r = n e g r o ; −>p a d r e −>p a d r e −> c o l o r = r o t a _ d ( x−>p a d r e −>p a d r e ) ;
x
x
rojo ;
}
else if
}
{
∗y
−>p a d r e −>p a d r e −>i z q u i e r d o −> c o l o r == r o j o ) { x−>p a d r e −> c o l o r = n e g r o ; y−> c o l o r = n e g r o ; x−>p a d r e −>p a d r e −> c o l o r = r o j o ; x = x−>p a d r e −>p a d r e ;
nodo
= x
;
( y && y
else if
}
{
−>p a d r e −>i z q u i e r d o ) { −>p a d r e ;
( x == x x = x
rota_d ( x ) ; }
−>p a d r e −> c o l o r = n e g r o ; −>p a d r e −>p a d r e −> c o l o r = r o t a _ i ( x−>p a d r e −>p a d r e ) ;
x x
rojo ;
} } }
return raiz
}
void
−> c o l o r
=
negro ;
nuevo ;
∗x ) { −>d e r e c h o ; x−>d e r e c h o = y−>i z q u i e r d o ; ( y−>i z q u i e r d o ) y−>i z q u i e r d o −>p a d r e y−>p a d r e = x−>p a d r e ; ( ! x−>p a d r e ) a r n : : r o t a _ i ( nodo
∗y
nodo
if if else if − else raiz
= x
= x;
= y;
−>p a d r e −>i z q u i e r d o ) −>i z q u i e r d o = y ;
( x == x
x
>p a d r e
x−>p a d r e −>d e r e c h o −>i z q u i e r d o = x ; x−>p a d r e = y ;
= y;
y
}
void
∗x ) { −>i z q u i e r d o ; x−>i z q u i e r d o = y−>d e r e c h o ; ( y−>d e r e c h o ) y−>d e r e c h o −>p a d r e y−>p a d r e = x−>p a d r e ; ( ! x−>p a d r e ) a r n : : rota_d ( nodo
∗y
nodo
if if else if − else raiz
= x
= x;
= y;
−>p a d r e −>d e r e c h o ) −>d e r e c h o = y ;
( x == x
x
>p a d r e
x−>p a d r e −>i z q u i e r d o −>d e r e c h o = x ; x−>p a d r e = y ;
= y;
y
}
∗ arn : : insertarABB ( ∗ aux = r a i z ;
a r n : : nodo nodo
int
c ,
int
d){
A.8. COLA DE PRIORIDADES (CABECERA)
if
new
71
(! raiz ){ raiz
=
nodo ( c ) ;
return while true if − if − − else raiz
−>d a t o
= d;
raiz ;
}
(
(c
){
<
aux
( aux
aux
>c l a v e ) {
>i z q u i e r d o )
= aux
>i z q u i e r d o ;
new
{
−>i z q u i e r d o = nodo ( c ) ; −>i z q u i e r d o −>d a t o = d ; aux−>i z q u i e r d o −>p a d r e = aux ; aux−>i z q u i e r d o ; aux
aux
return
}
else if else
}
{
−>d e r e c h o ) −>d e r e c h o ;
( aux
aux
= aux
new
{
−>d e r e c h o = nodo ( c ) ; −>d e r e c h o −>d a t o = d ; aux−>d e r e c h o −>p a d r e = aux ; aux−>d e r e c h o ; aux aux
return
} } } }
void
arn : : b o r r a r ( ) {
borrar ( raiz ) ;
}
void if
a r n : : b o r r a r ( nodo
∗x ) {
(x){
−>d e r e c h o ) ; −>i z q u i e r d o ) ;
borrar (x
if − − delete
borrar (x (x
x
}
>s i g u i e n t e )
>s i g u i e n t e
−>b o r r a r ( )
;
x;
}
A.8. Cola de prioridades (Cabecera) /∗
∗ Fichero : cola . h ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ C o n t e n i d o : D e c l a r a c i ó n d e l a c l a s e c o l a q u e i m p l e m e n t a una c o l a ∗ p r i o r i d a d e s de r e p e t i c i o n e s ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#ifndef #define #include
COLA_H COLA_H
de
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
72
#include #include using namespace class public
" automata . h"
std ;
cola { :
cola () ;
// PRE :
true
// POST :
Crea
// T( n ) :
O( 1 )
una
cola
vacia
la
cola
y
~cola () ;
// PRE :
true
// POST :
Vacia
// T( n ) :
O( 1 )
void
la
e n c o l a r ( automata : : r e p e t i c i o n
// PRE : // POST : // T( n ) :
// POST : // T( n ) :
void
memoria
&x ) ;
true introduce O( l o g
x
la
en
la
cola
n)
automata : : r e p e t i c i o n
// PRE :
cola
no
Devuelve
&p r i m e r o ( ) ;
esta la
vacia
repetición
de
mayor
longitud
de
la
cola
O( 1 )
desencolar () ;
// PRE :
la
cola
no
// POST :
Elimina
// T( n ) :
O( l o g
int
libera
size ()
// PRE : // POST : // T( n ) :
private
esta
de
la
vacia cola
el
elemento
de
mayor
longitud
n)
const return {
monticulo . s i z e ( ) ; } ;
true
Devuelve
el
numero
de
elementos
que
hay
en
la
cola
O( 1 )
:
v e c t o r
monticulo ;
};
#endif
A.9. Cola de prioridades /∗
∗ Fichero : c o l a . cc ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ C o n t e n i d o : I m p l e m e n t a c i ó n d e l a c l a s e c o l a q u e i m p l e m e n t a una c o l a ∗ p r i o r i d a d e s de r e p e t i c i o n e s ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#include #include #include #include
" c o l a . h"
de
A.10. ÁRBOL DE RANGOS (CABECERA)
#include #include using namespace
73
" automata . h"
std ;
cola : : cola () { monticulo . c l e a r ( ) ; }
c o l a : : ~ c o l a ( ) {}
void int while
c o l a : : e n c o l a r ( automata : : r e p e t i c i o n
&x ) {
m o n t i c u l o . push_back ( x ) ; pos
=
monticulo . s i z e ( )
( pos
>
0 &&
−
1;
m o n t i c u l o [ ( pos
− 1) / 2 ] .
longitud
swap( m o n t i c u l o [ p o s ] , pos
=
( pos
<
monticulo [ pos ] . l o n g i t u d ) {
m o n t i c u l o [ ( pos
− 1) / 2 ] )
;
− 1) / 2 ;
} }
return
automata : : r e p e t i c i o n
}
void
&c o l a : : p r i m e r o ( )
{
monticulo . f r o n t ( ) ;
cola : : desencolar () {
swap( m o n t i c u l o . f r o n t ( ) ,
int int while if
m o n t i c u l o . back ( ) ) ;
m o n t i c u l o . pop_back ( ) ; pos
=
0;
hijo ; (2 ((2
∗ p o s +1 ∗ p o s +1
<
( monticulo [2
else if
monticulo . s i z e ( ) ) {
==
monticulo . s i z e ( )
∗ pos + 2]. l o n g i t u d
hijo
=
2
∗ pos
+
1;
hijo
=
2
∗ pos
+
2;
( monticulo [ pos ] . l o n g i t u d
<
<
−
1)
||
monticulo [2
monticulo [ h i j o ] . longitud ) {
swap( m o n t i c u l o [ p o s ] , pos
=
else break
∗ pos + 1]. l o n g i t u d ) )
monticulo [ h i j o ] ) ;
hijo ;
}
}
;
}
A.10. Árbol de rangos (Cabecera) /∗
∗ Fichero : rangos . h ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ Contenido : D e c l a r a c i ó n de l a c l a s e a r b o l R a n g o s que implementa l a s ∗ de o c u p a c i o n y p r e g u n t a r por l i b r e de r a n g o s ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#ifndef #define
ARANGOS_H ARANGOS_H
funciones
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
74
#include using namespace class public
std ;
arbolRangos { :
arbolRangos ( ) ;
// PRE :
true
// POST :
crea
// T( n ) :
O( 1 )
un
arbol
de
rangos
con
todo
libre
y
libera
~arbolRangos ( ) ;
// PRE :
true
// POST :
borra
// T( n ) :
void
el
libre (r)
// POST :
ocupa
el
// T( n ) :
O( l o g
n)
la
memoria
devuelve
// T( n ) :
O( l o g
,
true
> &r ) ;
r
int int
true
// POST :
private enum enum struct int
rangos
,
rango
l i b r e ( pair<
// PRE :
de
int int
i n s e r t a r ( pair<
// PRE :
bool
arbol
O( n )
const
> &r )
si
el
rango
;
r
no
esta
ocupado
n)
:
colores
{ rojo ,
posicion nodo
ambos } ;
,
∗ izquierdo
,
∗ derecho ;
clave ;
posicion
info ;
colores
color ;
nodo ( ) :
padre ( 0 ) ,
void void void void void
segundo ,
{
∗ padre
nodo
negro } ;
{ primero ,
izquierdo (0) ,
derecho (0) {};
};
int
b o r r a r N o d o ( nodo insertar (
int
c ,
nodo
∗ insertarABB ( r o t a _ i ( nodo ∗n ) ; rota_d ( nodo ∗n ) ; p i n t a r ( nodo ∗n ) ;
nodo
∗ raiz
∗n ) ; posicion c ,
d) ;
posicion
p) ;
;
};
#endif
A.11. Árbol de rangos /∗
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
Fichero :
rangos . cc
Autor :
Pablo
Fecha :
2006
Proyecto : y
su
Contenido : de
PFC
Urcola
Irache
Algoritmos
aplicación
en
Implementación ocupacion
rojinegros
y
de
compresión
árboles de
la
preguntar
de
secuencias
biológicas
filogénicos clase por
arbolRangos
libre
de
que
rangos
implementa
usando
las
arboles
funciones
A.11. ÁRBOL DE RANGOS ∗ Licencia : ∗/
Ver
#include #include #include #include using namespace
fichero
75
LEEME
" r a n g o s . h"
std ;
arbolRangos : : arbolRangos ( ) { raiz
=
0;
}
arbolRangos : : ~ arbolRangos ( ) { borrarNodo ( r a i z ) ; }
void if else if
int int
arbolRangos : : i n s e r t a r ( pair < (r . first
==
r . second )
insertar ( r . first , (r . first
<
> &r ) {
ambos ) ; r . second ) {
insertar ( r . first ,
primero ) ;
i n s e r t a r ( r . second ,
else
,
segundo ) ;
}
{
insertar ( r . first ,
segundo ) ;
i n s e r t a r ( r . second ,
primero ) ;
} }
bool if return true int int ∗ while true if − if − else return − else if − if − else return − else return false
int int
arbolRangos : : l i b r e ( pair < (! raiz )
a
;
,
= min ( r . f i r s t ,
r . second ) ;
b = max ( r . f i r s t ,
r . second ) ;
nodo
aux
=
(
> &r )
const
raiz ;
){
( aux
>c l a v e
( aux
<
a){
>d e r e c h o ) aux
aux
>i n f o
−>d e r e c h o ;
= aux !=
primero ;
}
( aux
( aux
>
b){
>i z q u i e r d o )
>c l a v e
aux
aux
>i n f o
−>i z q u i e r d o
= aux
!=
;
segundo ;
}
;
}
}
void
arbolRangos : : i n s e r t a r (
nodo
∗x
=
−> c o l o r
x
while if if
=
insertarABB ( c ,
int
c ,
posicion
p){
p) ;
negro ;
!= r a i z && x−>p a d r e −> c o l o r == r o j o ) { −>p a d r e == x−>p a d r e −>p a d r e −>i z q u i e r d o ) { n o d o ∗ y = x−>p a d r e −>p a d r e −>d e r e c h o ; ( y−> c o l o r == r o j o ) { x−>p a d r e −> c o l o r = n e g r o ; y−> c o l o r = n e g r o ; x−>p a d r e −>p a d r e −> c o l o r = r o j o ; (x
(x
{
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
76
−>p a d r e −>p a d r e ;
x = x
else if
}
{
−>p a d r e −>d e r e c h o ) { −>p a d r e ;
( x == x x = x
rota_i ( x) ; }
−>p a d r e −> c o l o r = n e g r o ; −>p a d r e −>p a d r e −> c o l o r = r o t a _ d ( x−>p a d r e −>p a d r e ) ;
x
x
rojo ;
}
else if
}
{
∗ y = x−>p a d r e −>p a d r e −>i z q u i e r d o −> c o l o r == r o j o ) { x−>p a d r e −> c o l o r = n e g r o ; y−> c o l o r = n e g r o ; x−>p a d r e −>p a d r e −> c o l o r = r o j o ; x = x−>p a d r e −>p a d r e ;
nodo
;
(y
else if
}
{
−>p a d r e −>i z q u i e r d o ) { −>p a d r e ;
( x == x x = x
rota_d ( x ) ; }
−>p a d r e −> c o l o r = n e g r o ; −>p a d r e −>p a d r e −> c o l o r = r o t a _ i ( x−>p a d r e −>p a d r e ) ;
x x
rojo ;
} } } raiz
−> c o l o r
=
negro ;
}
void if
a r b o l R a n g o s : : b o r r a r N o d o ( nodo
∗n ) {
(n){
− −
b o r r a r N o d o ( n >i z q u i e r d o ) ;
delete
b o r r a r N o d o ( n >d e r e c h o ) ;
}
n;
}
if
a r b o l R a n g o s : : nodo
new
∗ arbolRangos
: : insertarABB (
(! raiz ){ raiz
=
nodo ( ) ;
−>c l a v e = c ; r a i z −> i n f o = p ;
raiz
}
return
raiz ;
while true if − if − − else ∗ aux
nodo
=
(
(c
raiz ;
){
<
aux
( aux
aux
>c l a v e ) {
>i z q u i e r d o )
= aux
{
>i z q u i e r d o ;
new
−>i z q u i e r d o = nodo ( ) ; −>i z q u i e r d o −>c l a v e = c ; aux−>i z q u i e r d o −> i n f o = p ; aux−>i z q u i e r d o −>p a d r e = aux ; aux−>i z q u i e r d o ; aux aux
} }
return
int
c ,
posicion
p){
A.12. REFERENCIAS (CABECERA)
else if else
77
{
−>d e r e c h o ) −>d e r e c h o ;
( aux
aux
= aux
new
{
−>d e r e c h o = nodo ( ) ; −>d e r e c h o −>c l a v e = c ; aux−>d e r e c h o −> i n f o = p ; aux−>d e r e c h o −>p a d r e = aux ; aux−>d e r e c h o ; aux aux
return
} } } }
void
a r b o l R a n g o s : : r o t a _ i ( nodo
∗y
nodo
if − − if − else if − else −
n >d e r e c h o (y
y
∗n ) {
−
= n >d e r e c h o ;
−>i z q u i e r d o ; y−>i z q u i e r d o −>p a d r e
= y
>i z q u i e r d o )
>p a d r e
= n;
−
= n >p a d r e ;
( ! n >p a d r e )
raiz
= n;
{
− −>i z q u i e r d o ) −>i z q u i e r d o = y ;
( n == n >p a d r e
n >p a d r e
−
n >p a d r e
−>d e r e c h o
= y;
}
−>i z q u i e r d o = − = y;
y
n;
n >p a d r e }
void
a r b o l R a n g o s : : rota_d ( nodo
∗y
nodo
if − − if − else if − else −
n >i z q u i e r d o (y
y
−>d e r e c h o ; y−>d e r e c h o −>p a d r e
= y
>d e r e c h o )
>p a d r e
∗n ) {
−
= n >i z q u i e r d o ;
= n;
−
= n >p a d r e ;
( ! n >p a d r e )
raiz
= n;
{
− −>d e r e c h o ) −>d e r e c h o = y ;
( n == n >p a d r e
n >p a d r e
−
n >p a d r e
−>i z q u i e r d o
= y;
}
−>d e r e c h o − =
y
= n;
n >p a d r e
y;
}
A.12. Referencias (Cabecera) /∗
∗ Fichero : r e f e r e n c i a . h ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ C o n t e n i d o : D e c l a r a c i ó n d e l a c l a s e r e f e r e n c i a p a r a a l m a c e n a r una ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
repetición
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
78
#ifndef #define #include #include #include using namespace struct
REFERENCIA_H_ REFERENCIA_H_
std ;
referencia {
// i n v a r i a n t e :
int int
first
bool
pair<
=
,
original . first
original ,
&&
o r i g i n a l . second
−
original .
repeticion ;
normal ;
referencia () {};
// PRE :
true
// POST :
true
// T( n ) :
O( 1 )
referencia (
// PRE :
int
// POST :
crea
// T( n ) :
O( 1 )
referencia (
// PRE :
int
a ,
a &o ,
&r ,
( o r i g i n a l ,
repeticion
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
80
normal
= n;
}
referencia : : referencia ( original
repeticion normal
const
referencia
&R) {
= R. o r i g i n a l ;
= R. r e p e t i c i o n ;
= R. normal ;
}
int int
r e f e r e n c i a : : r e f e r e n c i a ( pair< original
if
=
repeticion
o; =
int int
swap
> &o ,
int int
pair<
,
> &r ,
bool
n){
r ;
( repeticion . f i r s t
normal
,
,
<
original . first )
> >( o r i g i n a l ,
repeticion ) ;
}
bool return
referencia : :
operator
( original
==
==( r e f e r e n c i a
R. o r i g i n a l
&&
&R) {
repeticion
== R . r e p e t i c i o n ) ;
}
bool return
referencia : :
operator
( original
=
e
= AFD . b e g i n ( ) ;
int e
!=
l ){
AFD . e n d ( ) ;
l ){
nuevo ;
nuevo . l o n g i t u d
=
nuevo . p o s i c i o n e s
e
−>p r o f u n d i d a d ; e−>i d s ;
=
s o r t ( nuevo . p o s i c i o n e s . b e g i n ( ) , r e s u l t a d o . push_back ( n u e v o ) ;
nuevo . p o s i c i o n e s . end ( ) ) ;
e++){
A.15. AUTÓMATA
83
} }
return
AFD . c l e a r ( ) ;
}
void
resultado ;
a u t o m a t a : : AFN2AFD ( ) {
arn
ARN;
AFD . c l e a r ( ) ; estadoAFD
nuevo ;
nuevo . i n i c i a l i z a r ( ) ; nuevo . p r o f u n d i d a d
=
0;
n u e v o . i d s . push_back ( 0 ) ; ARN. i n s e r t a r ( 0 ,
nuevo . i d s ) ;
AFD . push_back ( n u e v o ) ;
int int do for int int if int if e
=
0;
insertados
=
1;
{
(
i
=
vector<
0;
>
i
<
4;
trans
( trans . s i z e () destino
( destino
= >
i ++){ t r a n s i c i o n (AFD [ e ] . i d s ,
= ARN. b u s c a r ( t r a n s ) ;
−1) {
!=
// y a
AFD [ e ] . t r a n s i c i o n [ i ]
=
estaba
definido
el
estado
destino ;
setProfundidad ( destino ,
else
i ) ;
1) {
AFD [ e ] . p r o f u n d i d a d
+
1) ;
}
{
nuevo . i n i c i a l i z a r ( ) ; nuevo . i d s
=
trans ;
nuevo . p r o f u n d i d a d
= AFD [ e ] . p r o f u n d i d a d
ARN. i n s e r t a r ( i n s e r t a d o s , AFD [ e ] . t r a n s i c i o n [ i ]
=
+
1;
trans ) ;
insertados ;
AFD . push_back ( n u e v o ) ; i n s e r t a d o s ++; }
else
}
{
AFD [ e ] . t r a n s i c i o n [ i ]
=
− 1;
} }
while e ++;
} }
(e
int int
vector<
>
vector<
for
!=
insertados ) ;
resultado ;
int
( vector<
transicion (
int
int
automata : : t r a n s i c i o n ( v e c t o r < >
∗i
>:: i t e r a t o r ,
s ,
return
>:: i t e r a t o r
resultado . erase ( fin ,
}
void if
= v . begin () ;
i
!=
int
s ){
v . end ( ) ;
i ++)
resultado ) ;
s o r t ( resultado . begin () , vector<
i
> &v ,
r e s u l t a d o . end ( ) ) ;
fin
=
unique ( r e s u l t a d o . begin ( ) ,
r e s u l t a d o . end ( ) ) ;
r e s u l t a d o . end ( ) ) ;
resultado ;
automata : : t r a n s i c i o n (
for int if ( estado (
== i
=
0) { 1;
i
int
&s a l i d a ) {
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
84
for int if (
i
= N +
1;
i
=
else if if
( e s t a d o >= N+1 &&
}
− 1) {
1 &&
e s t a d o &s a l i d a ) ;
de
bases
usando
una
de
bases
A.17. CODIFICADOR
// T( n ) :
void
unsigned char
b ) { BITS = b ; } ;
0 < b < 32
// POST : // T( n ) :
int
O( n )
setBits (
// PRE :
85
establece
getBits () {
// PRE :
true
// POST : // T( n ) :
el
tamaño
del
buffer
a
b
bits
O( 1 )
return
devuelve
el
BITS ; } ;
numero
de
bits
del
buffer
O( 1 )
private unsigned char :
};
BITS ;
#endif
A.17. Codi cador /∗
∗ Fichero : c o d i f i c a d o r . cc ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ C o n t e n i d o : I m p l e m e n t a c i ó n d e l a c l a s e c o d i f i c a d o r q u e comprime c a d e n a s ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#include #include #include #include #include #include void for int if
" c o d i f i c a d o r . h" " adn . h "
" e x c e p c i o n . h"
codificador : : codificar2 ( string
&b a s e s ,
salida . clear () ; (
i
=
0;
( bases [ i ]
i ==
<
bases . length () ;
s a l i d a . push_back ( }
( bases [ i ]
s a l i d a . push_back ( }
( bases [ i ]
s a l i d a . push_back ( }
( bases [ i ]
s a l i d a . push_back (
else throw
) ;
'c ' ){
true false
'g ' ){ ) ;
true true
==
s a l i d a . push_back (
}
) ;
i ++){
) ;
==
s a l i d a . push_back (
else if
false true
==
s a l i d a . push_back (
else if
) ;
> &s a l i d a ) {
'a ' ){
s a l i d a . push_back (
else if
false false
bool
vector<
) ;
' t ' ){ ) ; ) ;
{
} }
e x c e p c i o n ( " El
fichero
contiene
caracteres
no
válidos ") ;
de
adn
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
86
}
void ∗ unsigned long int unsigned long unsigned long int unsigned long unsigned long bool do
codificador : : codificar ( string
BITS =
&b a s e s ,
bool
vector<
l o g (NSIMBOLOS NSIMBOLOS) ; L,
H,
// numero
bpf ;
total ;
de
MITAD,
vector< i ,
// i n t e r v a l o
ampliaciones
CUARTO,
actual
centrales
que
del
> &s a l i d a ) {
manejamos
intervalo
TRESCUARTOS ;
∗
>
a c u m u l a d a s (NSIMBOLOS NSIMBOLOS,
1) ;
valor ;
paso ;
low_count ;
abortar ;
{
salida . clear () ;
unsigned long unsigned long unsigned int unsigned long unsigned int unsigned long unsigned int
f i l l ( acumuladas . b e g i n ( ) , L =
(
H =
(
a c u m u l a d a s . end ( ) ,
1) ;
) (0) ;
) (1= CUARTO && H < TRESCUARTOS) {
lo
marco
para
tenerlo
en
cuenta
//
intervalo
en
el
medio
luego
b p f ++;
// a c t u a l i z o L =
2
H =
2
∗ ∗
(L (H
el
− −
intervalo
CUARTO) ; CUARTO)
+
1;
}
a c u m u l a d a s [ v a l o r ]++; t o t a l ++; }
if
// e s c r i b i m o s
if
( i
== (H
el
fin
de
fichero
bases . length () ) {
−
L +
1 <
total ){
if throw true continue
BITS++;
( BITS >=
abortar
32)
=
excepcion (" Buffer
demasiado
pequeño " ) ;
;
;
}
paso
=
(H
−
L +
H = L +
paso
L = L +
paso
while if
∗ ∗
// Comprobamos
1)
/
si
el
( L >= MITAD
saco
for
los
intervalo
||
( L >= MITAD) {
//
total ;
− 1; ( t o t a l − 1) ; total
// H =
bits
bpf
>
0;
1...
true −− false
en
s a l i d a . push_back ( (;
L =
2
H =
2
else if
∗ ∗
(L (H
el
− −
bueno
o
hay
y
L =
1...
comun ) ;
bpf
)
s a l i d a . push_back (
// a c t u a l i z o
es
H < MITAD) {
) ;
intervalo
MITAD) ; MITAD)
+
1;
}
//
(H < MITAD) {
saco
for
los
bits
s a l i d a . push_back ( (;
bpf
>
0;
bpf
s a l i d a . push_back (
// a c t u a l i z o
} }
L =
2
H =
2
∗ ∗
el
L; H +
1;
// H =
false −− true
en
comun ) ;
)
) ;
intervalo
0...
y
L =
0...
que
ampliarlo
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
88
while
(
//
//
L >= CUARTO && H < TRESCUARTOS) {
lo
marco
para
tenerlo
en
cuenta
intervalo
en
el
medio
luego
b p f ++;
// a c t u a l i z o L =
2
H =
2
∗ ∗
(L (H
el
− −
intervalo
CUARTO) ; CUARTO)
+
1;
}
while
} }
//
if
( abortar ) ;
L < MITAD && H >= MITAD && ( L < CUARTO
// e s c r i b o
un
valor
dentro
s a l i d a . push_back ( (;
b p f +1 >
bpf
}
{
s a l i d a . push_back ( (;
b p f +1 >
0;
H >= TRESCUARTOS) H]
)
) ;
true −− false ) ;
bpf
)
s a l i d a . push_back (
}
||
[L,
) ;
0;
s a l i d a . push_back (
else for
intervalo
false −− true
( L < CUARTO) {
for
del
) ;
}
A.18. Decodi cador (Cabecera) /∗
∗ Fichero : d e c o d i f i c a d o r . h ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ Contenido : D e c l a r a c i ó n de l a c l a s e d e c o d i f i c a d o r que ∗ b a s e s d e adn ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#ifndef #define #include #include #include using namespace class public void
biológicas descomprime
cadenas
DECODIFICADOR_H DECODIFICADOR_H
" bstream . h"
std ;
decodificador { :
d e c o d i f i c a r ( ibstream
// PRE :
// POST : //
escribe
de
// T( n ) :
void
entrada
en
salida
usando
la
la
string
&s a l i d a ) ;
cadena
de
codificación
caracteres de
interpretada
al
leer
al
leer
rango
O( n )
d e c o d i f i c a r 2 ( ibstream
// PRE :
&e n t r a d a ,
string
&s a l i d a ) ;
true
// POST : //
&e n t r a d a ,
true
escribe
de
// T( n ) :
entrada
O( n )
en
salida
usando
la
dos
cadena bits
por
de
caracteres
base
de
adn
interpretada
de
A.19. DECODIFICADOR
89
#endif };
A.19. Decodi cador /∗
∗ Fichero : d e c o d i f i c a d o r . cc ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ Contenido : D e c l a r a c i ó n de l a c l a s e d e c o d i f i c a d o r que ∗ b a s e s d e adn ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#include #include #include #include #include #include #include #include using namespace void int
biológicas descomprime
" d e c o d i f i c a d o r . h" " adn . h " " bstream . h"
std ;
de co di fi ca do r : : d e c o d i f i c a r 2 ( ibstream N =
&e n t r a d a ,
string
&s a l i d a ) {
entrada . g e t l v ( ) ;
for int if if else
salida . clear () ; (
i
=
0;
i
< N;
i ++){
( entrada . g e t b i t () ) { ( entrada . g e t b i t ( ) )
salida
+=
't ' ;
salida
+=
'g ' ;
else if else
}
{
( entrada . g e t b i t ( ) )
salida
+=
'c ' ;
salida
+=
'a ' ;
} } }
void unsigned long unsigned char long unsigned long unsigned long unsigned long
d e c o d i f i c a d o r : : d e c o d i f i c a r ( ibstream
vector<
>
BITS =
&e n t r a d a ,
string
∗
a c u m u l a d a (NSIMBOLOS NSIMBOLOS,
&s a l i d a ) {
1) ;
entrada . g e t l v ( ) ;
salida . clear () ; L,
L =
0;
H =
(
H,
paso ,
MITAD,
CUARTO,
) (1= 0
// POST :
Devuelve
variable
// T( n ) :
cadena
cadena .
c a l c u l a r T a m a n o ( v e c t o r & r e p e t i c i o n e s ,
// PRE :
para
bits
n)
longitud
// T( n ) :
que
v e c t o r &r e p e t i c i o n e s , n,
O( r e s t o . l e n g t h ( )
0 < x 0
// POST :
componentes
lmin ,
longitudMinima (
// PRE :
//
repeticiones
las
repeticiones
const char int
codificados
// T( n ) :
las
las
&r e s t o ,
0 <
// POST :
//
las
son
n) ;
O( o r i g i n a l . l e n g t h ( ) )
string
//
l ,
True
// T( n ) :
#endif
la
O( 2 ^ n )
quitarPartesReferenciadas ( string
// POST :
};
contenido para
que
v e c t o r &r e p e t i c i o n e s ,
// PRE :
//
k
int
n > 0
el
//
int
el
parámetro
variable
mayor
int
un
O( 2 ^ n )
//
int
es
:
// POST :
int
k) ;
entrada
k > 0
v e c t o r &r e f e r e n c i a s ,
void
int
,
válidos ,
s a c a r R e f e r e n c i a s ( v e c t o r & r e p e t i c i o n e s ,
// PRE :
void
∗ salida
ficheros
O( l o g
de n)
la x
longitud
de
las
representacion
en
longitud
int
l ,
de
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
92
A.21. Compresor /∗
∗ Fichero : compresor . cc ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ C o n t e n i d o : C l a s e q u e comprime d e c a d e n a s d e adn ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace void
biológicas
" c om p re s o r . h" " automata . h" " r a n g o s . h" " adn . h " " r e f e r e n c i a . h" " bstream . h" " c o d i f i c a d o r . h" " c o l a . h"
" e x c e p c i o n . h"
std ;
compresor : : comprimir (
// l e o
if
la
ifstream
}
throw
entrada
const char
∗ fentrada
,
const char
∗ fsalida
,
int
k){
entrada ( fentrada ) ;
( entrada . f a i l ( ) ) {
string
excepcion ( " Error
al
abrir
el
fichero
de
entrada " ) ;
bases ;
g e t l i n e ( entrada ,
bases ) ;
entrada . c l o s e () ;
// c o n s t r u y o automata
int
// s a c o
las
lmin
el
automata
A( b a s e s . c _ s t r ( ) ,
=
repeticiones
bases . length () ) ;
mas
grandes
v e c t o r
// c o j o
las
referencias
v e c t o r
s o r t ( f i n a l . begin () ,
string
las
que
partes
repes
ordeno
por
tamaño
k) ;
= A. r e p e t i c i o n e s ( lmin ) ;
mas
bases
abarquen
final ,
lmin ,
bases . length () ) ;
f i n a l . end ( ) ,
referenciadas
anterior () ) ;
de
la
cadena
de
adn
y
almaceno
resto ;
q u i t a r P a r t e s R e f e r e n c i a d a s ( bases , escribir ( fsalida , }
las
final ;
saca rRefere ncias ( repes ,
// q u i t o
y
longitudMinima ( bases . l e n g t h ( ) ,
final ,
resto ,
final , lmin ,
resto ) ;
bases . length () ,
k) ;
lo
que
queda
A.21. COMPRESOR
void
93
int
int
c o m p r e s o r : : s a c a r R e f e r e n c i a s ( v e c t o r & r e p e t i c i o n e s , v e c t o r &r e f e r e n c i a s ,
arbolRangos
for if
cola
usados ;
l ,
n){
ordenadas ; ( v e c t o r : : i t e r a t o r i
!= (i
r e p e t i c i o n e s . end ( ) ;
−> p o s i c i o n e s
[0]
=
r e p e t i c i o n e s . begin () ;
0) {
mejor
=
ordenadas . primero ( ) ;
ordenadas . d e s e n c o l a r ( ) ;
if
int int
( mejor . l o n g i t u d
pair<
if
,
>
<
break
l )
;
o r i g i n a l ( p o s i c i o n ( mejor . p o s i c i o n e s [0]
p o s i c i o n ( mejor . p o s i c i o n e s [ 0 ] ,
int
( original . first swap<
if
∗
(2
>
>
for int int int es
(
k =
pair<
,
la
1; >
primera k <
o r i g i n a l . second ) ;
int
∗1.33∗ log ( o r i g i n a l
// o r i g i n a l
( c e i l (1.33
. f i r s t /2)
aparicion
1) ) ) {
del
sufijo k++){
rango ( p o s i c i o n ( mejor . p o s i c i o n e s [ k]
−
p o s i c i o n ( mejor . p o s i c i o n e s [ k ] ,
n) ) ; rangoInv
int
=
( rango . f i r s t
swap<
// r a n g o
if
∗ l o g ( mejor . l o n g i t u d −l )
+
mejor . p o s i c i o n e s . s i z e ( ) ;
m e j o r . l o n g i t u d +1 , n ) ,
bool if
es
mejor . p o s i c i o n e s [ k ] >
kesima
&&
( ! r e f . solapada () &&
n;
rango . second ) ;
repeticion
ref ( original ,
( ( ( ! r e f . nula ( )
>
rango . second )
>( r a n g o . f i r s t ,
la
referencia
del
rango ,
r e f . normal ) &&
sufijo
! rangoInv ) ; ||
! r e f . normal ) )
usados . l i b r e ( r e f . r e p e t i c i o n ) ) {
usados . i n s e r t a r ( r e f . r e p e t i c i o n ) ; r e f e r e n c i a s . push_back ( r e f ) ; } } } mejor . l o n g i t u d
−−;
ordenadas . e n c o l a r ( mejor ) ; } }
void int int while if while
compresor : : q u i t a r P a r t e s R e f e r e n c i a d a s ( s t r i n g
v e c t o r &r e p e t i c i o n e s , ref
i
=
=
string
&o r i g i n a l ,
&r e s t o ) {
0;
0;
( i
<
( ref
o r i g i n a l . length () ){
<
repeticiones . size () ){
( i
resto
< +=
repeticiones [ ref ] . repeticion . f i r s t ){ original [ i ];
i ++; } i
=
r e p e t i c i o n e s [ r e f ] . r e p e t i c i o n . second
r e f ++;
else
}
{
resto i ++;
+=
l o n g i t u d +1 , n ) ,
o r i g i n a l . second )
>( o r i g i n a l . f i r s t ,
mejor . l o n g i t u d 2
− mejor .
n) ) ;
original [ i ];
+
1;
+
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
94
} } }
void
int true
compresor : : e s c r i b i r ( string
bool
&r e s t o ,
agresivo
obstream
bool
vector< {
n,
v e c t o r &r e p e t i c i o n e s ,
k){
; k) ;
c ; >
restoc ;
c . c odif ica r2 ( resto ,
catch throw try
nombre ,
s a l i d a ( nombre ,
codificador
try
=
const char ∗ int int
lmin ,
restoc ) ;
}
( excepcion
&e ) {
e ;
}
{
c . c o d i f i c a r ( resto ,
catch
restoc ) ;
}
=
}
if
try
false
( excepcion
agresivo
&e ) {
( restoc . size ()
;
>
2
∗ resto
. length ()
||
agresivo
{
c . co dif icar 2 ( resto ,
catch throw
==
false
){
restoc ) ;
}
( excepcion
}
agresivo
=
}
// e s c r i b o
&e ) {
e ;
el
false
;
parametro
k
para
s a l i d a . pu t ( s a l i d a . getK ( ) ,
los
enteros
de
longitud
variable
8) ;
s a l i d a . putlv ( lmin ) ; s a l i d a . putlv ( r e p e t i c i o n e s . s i z e () ) ;
int int for
// e s c r i b o
las
anterior anteriorR
referencias =
0;
=
0;
( v e c t o r : : i t e r a t o r r
!=
r e p e t i c i o n e s . end ( ) ;
r
=
r e p e t i c i o n e s . begin () ;
r ++){
−> o r i g i n a l . f i r s t − r −> r e p e t i c i o n . f i r s t − −> r e p e t i c i o n . f i r s t − a n t e r i o r R ) ; s a l i d a . p u t l v ( r −>l o n g i t u d ( ) − l m i n ) ; s a l i d a . p u t b i t ( r −>n o r m a l ) ; a n t e r i o r = r −> o r i g i n a l . f i r s t − r −> r e p e t i c i o n . f i r s t ; a n t e r i o r R = r −> r e p e t i c i o n . s e c o n d ; salida . putlvs ( r s a l i d a . putlv ( r
} salida . putbit ( agresivo ) ;
if else
el
// e s c r i b o
las
// e s c r i b o
tamaño
del
// marco buffer
la
del
codificacion codificador
( agresivo )
s a l i d a . putlv ( c . getBits () ) ;
s a l i d a . putlv ( resto . length () ) ;
bases
no
referenciadas
de
referencias
s a l i d a . put ( r e s t o c ) ;
// e s c r i b o
el
numero
salida . close () ; }
int
compresor : : longitudMinima (
int
n,
int
k){
agresiva
anterior ) ;
A.21. COMPRESOR
int int int int int while
derecha
D =
= n
=
=
−
izquierda
( derecha
+
k) ;
n,
k) ;
1 && M >=
( (M <
0 && D >
izquierda
=
>
1) {
izquierda ) /2;
f u n c i o n ( medio , (M
medio ;
0 && D <
0) ) {
medio ;
= M;
else
}
{
derecha
=
medio ;
D = M; } }
}
return
int double return
derecha ;
int int double double
compresor : : f u n c i o n (
int
factor 2
=
∗x −
}
int
int
int
x,
(k)/
( ceil ( factor
int
n, (k
k){
− 1) ;
∗ log (x)
+
2
∗ f a c t o r ∗ log (n/3)
l ,
n){
int int int for
referencias ;
sacarReferencias ( repeticiones , tamano
=
2
anterior
referencias ,
!=
0;
r e f e r e n c i a s . end ( ) ;
−=2 ∗
n) ;
0;
=
( v e c t o r : : i t e r a t o r r
l ,
∗n ;
=
anteriorR
tamano
r
=
r e f e r e n c i a s . begin () ;
r ++){
−>l o n g i t u d ( ) ; −> o r i g i n a l . f i r s t − r −> r e p e t i c i o n . f i r s t − l o n g B i t s ( r −> r e p e t i c i o n . f i r s t − a n t e r i o r R ) ; ( r −>l o n g i t u d ( ) − l ) ; r
tamano+=l o n g B i t s ( r tamano += tamano += tamano++; anterior anteriorR
return
=
r
=
−> o r i g i n a l . f i r s t − r −> r e p e t i c i o n r −> r e p e t i c i o n . s e c o n d ;
}
int int int
tamano ;
compresor : : l o n g B i t s ( grupos ; l
=
grupos
if return
int
log (x) ;
=
l /3;
( l %3 !=
}
1) ) ;
c o m p r e s o r : : c a l c u l a r T a m a n o ( v e c t o r & r e p e t i c i o n e s ,
v e c t o r
}
+
0)
grupos
g r u p o s ++;
∗4;
x){
. first ;
a n t e r i o r ) +1;
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
96
A.22. Descompresor (Cabecera) /∗
∗ Fichero : descompresor . h ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l a f i l o g é n i c o s ∗ C o n t e n i d o : D e c l a r a c i ó n d e l a c l a s e d e s c o m p r e s o r q u e d e s c o m p r i m e un ∗ d e adn c o m p r i m i d o s ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#ifndef #define class public void
ficheros
DESCOMPRESOR_H DESCOMPRESOR_H
descompresor { : descomprimir (
// PRE :
fentrada
// POST : //
el
fichero
compresión
// T( n ) :
const char
es
el
∗ fentrada
nombre
fsalida
de
un
,
const char
fichero
contiene
la
de
∗fsalida ) ;
adn
secuencia
comprimido biológica
sin
alguna
O( n )
};
#endif
A.23. Descompresor /∗
∗ Fichero : descompresor . cc ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ Contenido : Implementación de l a c l a s e d e s c o m p r e s o r ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#include #include #include #include #include #include #include #include #include #include #include using namespace void if throw
biológicas
" d e s c o m p r e s o r . h" " bstream . h"
" r e f e r e n c i a . h" " d e c o d i f i c a d o r . h"
" e x c e p c i o n . h"
std ;
descompresor : : descomprimir (
ibstream
entrada ( fentrada ) ;
const char
∗ fentrada
,
const char
( entrada . f a i l ( ) ) { excepcion (" Fallo
}
al
abrir
el
fichero
de
entrada " ) ;
∗ fsalida ){
A.23. DESCOMPRESOR
int
// l e o
el
primer
k =
97
byte
entrada . get (8) ;
e n t r a d a . setK ( k ) ;
int
// l o n g i t u d lmin
int
// l e o
el
int int int int for
entrada . g e t l v ( ) ;
numero
nref
// l e o
minima
=
=
las
de
referencias
entrada . g e t l v ( ) ;
referencias
v e c t o r anterior
=
anteriorR
repeticiones ( nref ) ;
0;
=
0;
leido ; longitud ; ( v e c t o r : : i t e r a t o r r
!=
leido
r e p e t i c i o n e s . end ( ) ;
=
r
=
r e p e t i c i o n e s . begin () ;
r ++){
entrada . g e t l v s ( ) ;
−> r e p e t i c i o n . f i r s t r −> o r i g i n a l . f i r s t = r
longitud
=
=
entrada . g e t l v ()
leido
+
entrada . g e t l v ( )
r
+
+
anteriorR ;
−> r e p e t i c i o n
. first
+
anterior ;
lmin ;
−> o r i g i n a l . s e c o n d = r −> o r i g i n a l . f i r s t + l o n g i t u d − 1 ; −> r e p e t i c i o n . s e c o n d = r −> r e p e t i c i o n . f i r s t + l o n g i t u d − r −>n o r m a l = e n t r a d a . g e t b i t ( ) ; a n t e r i o r = r −> o r i g i n a l . f i r s t − r −> r e p e t i c i o n . f i r s t ; a n t e r i o r R = r −> r e p e t i c i o n . s e c o n d ; r
r
}
// l e o
las
string
bases
no
referenciadas
y
las
decodifico
resto ;
if else
decodificador
d;
( entrada . g e t b i t ( ) )
d . d e c o d i f i c a r ( entrada ,
resto ) ;
d . d e c o d i f i c a r 2 ( entrada ,
resto ) ;
entrada . c l o s e () ;
//
reconstruyo
int int int while if while string i
la
cadena
original
bases ;
=
// i n d i c e
0;
ref
=
0;
pos
=
0;
de
// i n d i c e
la de
cadena resto
( pos
<
resto . length () ){
( ref
<
repeticiones . size () ){
( i
bases
< +=
reconstruida
repeticiones [ ref ] . repeticion . f i r s t ){ r e s t o [ pos ] ;
p o s ++; i ++;
if
}
for int
( r e p e t i c i o n e s [ r e f ] . normal ) ( j
=
bases i
=
repeticiones [ ref ] . original . f irst ;
j
=
r e p e t i c i o n e s [ r e f ] . o r i g i n a l . second ;
repeticiones [ ref ] . original . first ;
+=
j ++)
bases [ j ] ;
bases [ j ] ;
r e p e t i c i o n e s [ r e f ] . r e p e t i c i o n . second
r e f ++; }
=
r e p e t i c i o n e s [ r e f ] . o r i g i n a l . second ;
+=
( j
j
+
1;
j
−−)
1;
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
98
else
{
bases
+=
r e s t o [ pos ] ;
p o s ++; } }
ofstream salida
salida ( fsalida ) ;
add ( ∗ l f i c h e r o ) ; vbox−>add ( ∗ l t e n t r a d a ) ; vbox−>add ( ∗ l t s a l i d a ) ; vbox−>add ( ∗ l t i e m p o ) ; vbox−>add ( ∗ hbbox ) ; add ( ∗ v b o x ) ;
hbbox vbox
s e t _ t i t l e ( " Resultado
de
la
compresión " ) ;
show_all_children ( ) ; set_default_size (350 ,
300) ;
show ( ) ; }
A.28. Ventana principal (Cabecera) /∗
∗ Fichero : ventanaPrincipal . h ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ Contenido : D e c l a r a c i ó n de l a c l a s e V e n t a n a P r i n c i p a l que c r e a e l ∗ gráfico ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#ifndef #define
VENTANAPRINCIPAL_H VENTANAPRINCIPAL_H
interfaz
A.28. VENTANA PRINCIPAL (CABECERA)
#include #include #include #include #include #include #include #include #include #include using namespace using namespace class public
101
Gtk ; std ;
VentanaPrincipal
public
:
:
Window
{
VentanaPrincipal () ;
private void void
~VentanaPrincipal () ; :
string
directorio ;
cargarConfiguracion () ; ejecutar () ;
∗ b o t o n P r o c e s a r , ∗ botonAyuda , ∗ b o t o n S a l i r ∗ botonGuardar ; RadioButton ∗ rbComprimir , ∗ r b D e s c o m p r i m i r ;
Button
void void bool void void enum
modoDescomprimir ( ) ; accionComprimir ;
∗ rbmio
usarDnax ( ) ; algoritmo
metodo ;
∗ fsAbrir
void void
Entry
Image
#endif
∗ fsGuardar ;
fsAbrirCANCEL ( ) ; abrir () ; fs Gua rda rOK ( ) ; fsGuardarCANCEL ( ) ; guardar ( ) ;
∗ dialogoAyuda ;
ayudar ( ) ;
∗ etiquetaEntrada
,
∗ etiquetaSalida
etiquetas () ;
∗ entryEntrada
,
∗ entrySalida
modificar () ;
SpinButton
};
,
fsAbrirOK ( ) ;
Dialog
Label
DNAX} ;
botones ( ) ;
FileSelection
void
{MIO ,
nombres [ 2 ] ;
algoritmo
void
∗ rbdnax ;
,
usarMio ( ) ;
string
void void void void void void
∗ botonAbrir
modoComprimir ( ) ;
RadioButton
void
,
∗ parametro ;
entries () ;
∗ dibujo
;
;
,
∗ etiquetaParametro ;
,
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
102
A.29. Ventana principal /∗
∗ Fichero : v e n t a n a P r i n c i p a l . cc ∗ Autor : P a b l o U r c o l a I r a c h e ∗ Fecha : 2006 ∗ P r o y e c t o : PFC A l g o r i t m o s d e c o m p r e s i ó n d e s e c u e n c i a s b i o l ó g i c a s ∗ y s u a p l i c a c i ó n en á r b o l e s f i l o g é n i c o s ∗ Contenido : Implementación de l a c l a s e V e n t a n a P r i n c i p a l que c r e a ∗ gráfico ∗ L i c e n c i a : Ver f i c h e r o LEEME ∗/
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace using namespace using namespace
el
interfaz
" v e n t a n a P r i n c i p a l . h"
" c om p re s o r . h" " f p . h"
" d e s c o m p r e s o r . h" " e x c e p c i o n . h"
< s t d i o . h> " d i a l o g o . h"
Gtk ; SigC ; std ;
VentanaPrincipal : : VentanaPrincipal () { n o m b r e s [ MIO ] n o m b r e s [DNAX]
=
"Mi
=
Algoritmo " ;
"DnaX" ;
s e t _ t i t l e ( " Compresor / D e s c o m p r e s o r
de
secuencias
biológicas ") ;
set_default_icon_from_file ( " imagenes / icono . g i f " ) ;
cargarConfiguracion () ; botones ( ) ; etiquetas () ; entries () ;
VBox
∗ vbox = ∗ hbox
HBox
dibujo
=
new new new
VBox ( ) ;
=
HBox ( ) ;
I m a g e ( " i m a g e n e s / adn . j p g " ) ;
−>add ( ∗ d i b u j o ) ;
hbox
VBox
∗ vbox2
=
AspectFrame
new
new
VBox ( ) ;
∗ frame2
=
AspectFrame ( " A l g o r i t m o " ,
ALIGN_CENTER,
A.29. VENTANA PRINCIPAL
new
ALIGN_CENTER,
1.0 ,
103
true
) ;
∗ hbox3 = HBox ( ) ; hbox3−>p a c k _ s t a r t ( ∗ r b m i o ) ; hbox3−>p a c k _ s t a r t ( ∗ r b d n a x ) ; f r a m e 2 −>add ( ∗ h b o x 3 ) ; vbox2 −>add ( ∗ f r a m e 2 ) ; AspectFrame ∗ f r a m e = AspectFrame ( " A c c i ó n " , HBox
new
ALIGN_CENTER,
new true
1.0 ,
ALIGN_CENTER,
) ;
∗ hbox2 = HBox ( ) ; −>p a c k _ s t a r t ( ∗ r b C o m p r i m i r ) ; hbox2−>p a c k _ s t a r t ( ∗ r b D e s c o m p r i m i r ) ; f r a m e −>add ( ∗ h b o x 2 ) ; vbox2 −>add ( ∗ f r a m e ) ; HBox
hbox2
new
∗ layout = Table ( 3 , 3) ; −>a t t a c h ( ∗ e t i q u e t a E n t r a d a , 0 , 1 , 0 , 1 ) ; l a y o u t −>a t t a c h ( ∗ e t i q u e t a S a l i d a , 0 , 1 , 1 , 2) ; l a y o u t −>a t t a c h ( ∗ e t i q u e t a P a r a m e t r o , 0 , 1 , 2 , 3) ; l a y o u t −>a t t a c h ( ∗ e n t r y E n t r a d a , 1 , 2 , 0 , 1) ; l a y o u t −>a t t a c h ( ∗ e n t r y S a l i d a , 1 , 2 , 1 , 2) ; l a y o u t −>a t t a c h ( ∗ p a r a m e t r o , 1 , 2 , 2 , 3 , EXPAND) ; l a y o u t −>a t t a c h ( ∗ b o t o n A b r i r , 2 , 3 , 0 , 1 , FILL | EXPAND,
Table
layout
EXPAND, layout
5) ;
−>a t t a c h ( ∗ b o t o n G u a r d a r
EXPAND,
,
2,
3,
1,
2,
FILL | EXPAND,
5) ;
−>add ( ∗ l a y o u t ) ; −>add ( ∗ v b o x 2 ) ; vbox−>add ( ∗ hbox ) ; vbox2
hbox
new
∗ hbbox = HButtonBox (BUTTONBOX_SPREAD, −>add ( ∗ botonAy uda ) ; hbbox−>add ( ∗ b o t o n P r o c e s a r ) ; hbbox−>add ( ∗ b o t o n S a l i r ) ; vbox−>add ( ∗ hbbox ) ; add ( ∗ v b o x ) ; HButtonBox hbbox
accionComprimir
=
true
;
show_all_children ( ) ;
set_default_size (500 ,
250) ;
}
VentanaPrincipal : : ~ VentanaPrincipal () {
delete delete delete delete delete delete delete delete delete delete delete delete delete delete delete delete
// b o t o n e s botonProcesar ; botonSalir ; botonAy uda ; botonAbrir ; botonGuardar ; rbComprimir ; rbDescomprimir ; rbmio ; rbdnax ;
// e t i q u e t a s etiquetaEntrada ; etiquetaSalida ; etiquetaParametro ;
// e n t r i e s entryEntrada ; entrySalida ; parametro ;
// d i b u j o s dibujo ;
0) ;
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
104
}
void
new
VentanaPrincipal : : botones ( ) {
botonProcesar
botonProcesar
=
B u t t o n ( S t o c k : : EXECUTE) ;
−>s i g n a l _ c l i c k e d
new
( ) . c o n n e c t ( mem_fun (
∗
&V e n t a n a P r i n c i p a l : : e j e c u t a r ) ) ; botonSalir
=
new
&V e n t a n a P r i n c i p a l : : h i d e ) ) ; botonA yuda botonAyuda
=
new
( ) . c o n n e c t ( mem_fun (
botonAbrir
=
this
∗
this
B u t t o n ( S t o c k : : OPEN) ;
−>s i g n a l _ c l i c k e d
new
( ) . c o n n e c t ( mem_fun (
&V e n t a n a P r i n c i p a l : : a b r i r ) ) ; botonGuardar botonGuardar
=
B u t t o n ( S t o c k : : SAVE) ;
−>s i g n a l _ c l i c k e d
new
this
∗
B u t t o n ( S t o c k : : HELP) ;
−>s i g n a l _ c l i c k e d
&V e n t a n a P r i n c i p a l : : a y u d a r ) ) ;
botonAbrir
( ) . c o n n e c t ( mem_fun (
∗
&V e n t a n a P r i n c i p a l : : g u a r d a r ) ) ; rbComprimir
=
( ) . c o n n e c t ( mem_fun (
∗
&V e n t a n a P r i n c i p a l : : modoComprimir ) ) ;
new
R a d i o B u t t o n : : Group rbDescomprimir rbDescomprimir
=
rbmio
=
grupo
=
rbComprimir
R a d i o B u t t o n ( "Mi
this
( ) . c o n n e c t ( mem_fun (
new
rbdnax
;
∗
this
Algoritmo " ) ;
( ) . c o n n e c t ( mem_fun (
∗
&V e n t a n a P r i n c i p a l : : u s a r M i o ) ) ; R a d i o B u t t o n : : Group
,
" Descomprimir " ) ;
= MIO ;
=
,
;
−>s i g n a l _ c l i c k e d
rbdnax
,
−>g e t _ g r o u p ( )
RadioButton ( grupo ,
−>s i g n a l _ c l i c k e d
−>s e t _ a c t i v e ( )
metodo rbmio
new
,
this
&V e n t a n a P r i n c i p a l : : m o d o D e s c o m p r i m i r ) ) ;
rbmio
,
RadioButton ( " Comprimir " ) ;
−>s e t _ a c t i v e ( ) ; r b C o m p r i m i r −>s i g n a l _ c l i c k e d rbComprimir
grupo2
=
rbmio
−>s i g n a l _ c l i c k e d
this
,
−>g e t _ g r o u p ( )
RadioButton ( grupo2 ,
"DnaX" ) ;
( ) . c o n n e c t ( mem_fun (
&V e n t a n a P r i n c i p a l : : u s a r D n a x ) ) ;
∗
this
;
,
}
void
etiquetaSalida
= =
etiquetaParametro }
void
new new new
VentanaPrincipal : : etiquetas () {
etiquetaEntrada
Label ( " Fichero
Label ( " Fichero
=
new
de de
entryEntrada
Label ( " Parámetro " ) ;
=
Entry ( ) ;
−>s i g n a l _ c h a n g e d ( )
new new
. c o n n e c t ( mem_fun (
&V e n t a n a P r i n c i p a l : : m o d i f i c a r ) ) ; entrySalida parametro
=
=
Entry ( ) ;
SpinButton ( ) ;
−> s e t _ d i g i t s ( 0 ) ; −>s e t _ n u m e r i c ( ) ; p a r a m e t r o −>s e t _ r a n g e ( 1 , 2 0 ) ; p a r a m e t r o −>s e t _ v a l u e ( 4 ) ; p a r a m e t r o −>s e t _ i n c r e m e n t s ( 1 ,
parametro
parametro
5) ;
}
void if
entrada " ) ; salida ") ;
VentanaPrincipal : : e n t r i e s () {
entryEntrada
VentanaPrincipal : : modificar () {
string
,
B u t t o n ( S t o c k : : CLOSE) ;
−>s e t _ f l a g s (CAN_DEFAULT) ; b o t o n S a l i r −>s i g n a l _ c l i c k e d ( ) . c o n n e c t ( mem_fun ( ∗ botonSalir
this
extension ;
( accionComprimir )
∗
this
,
,
A.29. VENTANA PRINCIPAL
else switch case break case break extension
=
105
" . cca " ;
{
( metodo ) {
MIO :
extension
=
" . dca " ;
=
" . y" ;
;
DNAX:
extension ;
}
}
if else
entrySalida
−>g e t _ t e x t ( ) . empty ( ) ) −>s e t _ t e x t ( e n t r y E n t r a d a −>g e t _ t e x t ( )
entrySalida
−>s e t _ t e x t ( " " ) ;
( ! entryEntrada
+
extension ) ;
}
void if
VentanaPrincipal : : ejecutar () {
FILE
∗f
=
fopen ( entryEntrada
(! f ){
∗ aviso
MessageDialog
true − delete return " El
aviso
fichero ,
de
=
−>g e t _ t e x t ( )
new
entrada
MESSAGE_ERROR,
. c_str ( ) ,
MessageDialog ( no
se
puede
∗
this
abrir
"r") ;
,
para
lectura " ,
BUTTONS_OK) ;
>r u n ( ) ; aviso ;
;
}
fclose ( f ) ;
if
f
=
fopen ( entrySalida
−>g e t _ t e x t ( )
(! f ){
∗ aviso
MessageDialog
true − delete return " El
aviso
fichero ,
de
=
new
salida
MESSAGE_ERROR,
. c_str ( ) ,
MessageDialog (
no
se
puede
"w" ) ;
∗
this
abrir
,
para
escritura " ,
BUTTONS_OK) ;
>r u n ( ) ; aviso ;
;
}
switch case if
fclose ( f ) ; ( metodo ) { MIO : ( accionComprimir ) {
try
compresor
c ;
{
time_t
inicio
=
time ( 0 ) ;
−>g e t _ t e x t ( ) −>g e t _ t e x t ( ) . c _ s t r ( ) , ( p a r a m e t r o −>g e t _ v a l u e ( ) ) ) ;
c . comprimir ( entryEntrada
int
. c_str ( ) ,
entrySalida
time_t FILE FILE
fin
∗ fe ∗ fs
=
time ( 0 ) ;
fopen ( entryEntrada
=
fopen ( entrySalida
f s e e k ( fe ,
0,
SEEK_END) ;
fseek ( fs ,
0,
SEEK_END) ;
dialogoInfo
new
∗ i n f o= dialogoInfo ( −>g e t _ t e x t ( ) , n o m b r e s [ metodo ]
entryEntrada f t e l l ( fe ) ,
f t e l l ( fs ) ,
// i n f o −>r u n ( ) ; fclose ( fe ) ; fclose ( fs ) ;
catch
−>g e t _ t e x t ( ) . c _ s t r ( ) −>g e t _ t e x t ( ) . c _ s t r ( ) ,
=
}
( excepcion
&e ) {
difftime ( fin ,
,
inicio )) ;
,
"r") ; "r") ;
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
106
true − delete catch
∗ aviso
MessageDialog
aviso
,
=
new
MESSAGE_ERROR,
MessageDialog (
∗
this
∗
this
BUTTONS_OK) ;
,
e . info () ,
>r u n ( ) ; aviso ;
}
( . . . ) {
∗ aviso
MessageDialog " Algo
ha
salido
=
new
mal " ,
BUTTONS_OK) ;
delete aviso
}
else
−>r u n ( )
true
MessageDialog ( ,
,
MESSAGE_ERROR,
;
aviso ;
}
{
descompresor
d;
Glib : : u s t r i n g
try
MessageType
mensaje ( " Descompresión
tipo
finalizada
con
éxito ") ;
= MESSAGE_INFO ;
{
d . descomprimir ( entryEntrada entrySalida
catch
−>g e t _ t e x t ( )
−>g e t _ t e x t ( )
. c_str ( ) ,
. c_str ( ) ) ;
}
( excepcion
mensaje tipo
catch
=
&e ) {
e . info () ;
= MESSAGE_ERROR;
}
( . . . ) {
mensaje tipo
=
" Algo
ha
salido
}
true − delete break case if
∗ aviso
MessageDialog
aviso
mal " ;
= MESSAGE_ERROR;
,
tipo ,
=
new
MessageDialog (
BUTTONS_OK) ;
∗
this
,
mensaje ,
>r u n ( ) ; aviso ;
}
;
DNAX:
( accionComprimir ) {
string
args [ 4 ] ;
args [ 0 ]
=
" dnaX " ;
−O" ;
args [ 1 ]
=
args [ 2 ]
=
entrySalida
char ∗ for int
=
entryEntrada
args [ 3 ]
"
−>g e t _ t e x t ( ) ; −>g e t _ t e x t ( )
;
argsc [ 4 ] ;
(
char
i
=
0;
argsc [ i ]
=
(
try
time_t
inicio
i
=
<
4;
i ++)
∗) args
[ i ] . c_str ( ) ;
time ( 0 ) ;
{
dnax ( 4 , time_t
FILE FILE
argsc ) ; fin
∗ fe ∗ fs
=
time ( 0 ) ;
−>g e t _ t e x t ( ) . c _ s t r ( ) −>g e t _ t e x t ( ) . c _ s t r ( ) ,
=
fopen ( entryEntrada
=
fopen ( entrySalida
f s e e k ( fe ,
0,
SEEK_END) ;
fseek ( fs ,
0,
SEEK_END) ;
dialogoInfo
new
∗ i n f o= dialogoInfo ( −>g e t _ t e x t ( ) , n o m b r e s [ metodo ]
entryEntrada f t e l l ( fe ) ,
ft ell ( fs ) ,
difftime ( fin ,
,
"r") ; "r") ;
,
inicio )) ;
// i n f o −>r u n ( ) ; fclose ( fe ) ; fclose ( fs ) ;
catch
}
( excepcion
MessageDialog
&e ) {
∗ aviso
=
new
MessageDialog (
∗
this
,
e . info () ,
A.29. VENTANA PRINCIPAL
true − delete catch aviso
,
107
MESSAGE_ERROR,
BUTTONS_OK) ;
>r u n ( ) ; aviso ;
}
( . . . ) {
∗ aviso
MessageDialog " Algo
ha
salido
=
new
mal " ,
BUTTONS_OK) ;
delete aviso
}
else
−>r u n ( )
true
MessageDialog ( ,
∗
this
,
MESSAGE_ERROR,
;
aviso ;
}
{
string
args [ 3 ] ;
args [ 0 ]
=
" dnaX " ;
−d " ;
args [ 1 ]
=
"
char ∗ for int
=
entryEntrada
args [ 2 ]
−>g e t _ t e x t ( )
;
argsc [ 3 ] ;
(
char
i
=
0;
argsc [ i ]
=
(
Glib : : u s t r i n g
try
MessageType
i
<
3;
i ++)
∗) args
[ i ] . c_str ( ) ;
mensaje ( " Descompresión
tipo
finalizada
con
éxito ") ;
= MESSAGE_INFO ;
{
dnax ( 3 ,
catch
argsc ) ;
}
( excepcion
mensaje tipo
catch
=
&e ) {
e . info () ;
= MESSAGE_ERROR;
}
( . . . ) {
mensaje tipo
=
" Algo
ha
salido
}
true − delete break default
MessageDialog
aviso
mal " ;
= MESSAGE_ERROR;
,
∗ aviso
tipo ,
=
new
MessageDialog (
∗
BUTTONS_OK) ;
this
,
mensaje ,
>r u n ( ) ; aviso ;
}
; :
MessageDialog " Algoritmo
delete aviso
}
−>r u n ( )
∗ aviso no
=
new
true
MessageDialog (
reconocido " ,
;
,
∗
this
,
MESSAGE_ERROR,
BUTTONS_OK) ;
aviso ;
}
void
new
VentanaPrincipal : : abrir () {
fsAbrir
=
false
FileSelection (" Elija
el
fichero
−>s e t _ s e l e c t _ m u l t i p l e ( ) ; f s A b r i r −>g e t _ o k _ b u t t o n ( )−> s i g n a l _ c l i c k e d
fsAbrir
de
( ) . c o n n e c t ( mem_fun (
&V e n t a n a P r i n c i p a l : : f s A b r i r O K ) ) ; fsAbrir
−>g e t _ c a n c e l _ b u t t o n ( )−> s i g n a l _ c l i c k e d
delete
fsAbrir
}
void
−>s e t _ f i l e n a m e ( d i r e c t o r i o ) ; −>r u n ( ) ; fsAbrir ;
V e n t a n a P r i n c i p a l : : fsAbrirOK ( ) {
entryEntrada
∗
this
( ) . c o n n e c t ( mem_fun (
&V e n t a n a P r i n c i p a l : : fsAbrirCANCEL ) ) ; fsAbrir
entrada " ) ;
−>s e t _ t e x t ( f s A b r i r −>g e t _ f i l e n a m e ( ) ) ;
∗
,
this
,
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
108
fsAbrir
−>h i d e ( )
;
}
void
V e n t a n a P r i n c i p a l : : fsAbrirCANCEL ( ) {
fsAbrir
−>h i d e ( )
;
}
void
new
VentanaPrincipal : : guardar ( ) {
fsGuardar
=
false
FileSelection (" Elija
el
fichero
−>s e t _ s e l e c t _ m u l t i p l e ( ) ; f s G u a r d a r −>g e t _ o k _ b u t t o n ( )−> s i g n a l _ c l i c k e d fsGuardar
de
salida ") ;
( ) . c o n n e c t ( mem_fun (
∗
&V e n t a n a P r i n c i p a l : : fsG uar dar OK ) ) ; fsGuardar
−>g e t _ c a n c e l _ b u t t o n ( )−> s i g n a l _ c l i c k e d
( ) . c o n n e c t ( mem_fun (
&V e n t a n a P r i n c i p a l : : fsGuardarCANCEL ) ) ; fsGuardar
delete
fsGuardar
}
void
−>s e t _ f i l e n a m e ( d i r e c t o r i o ) ; −>r u n ( ) ;
fsGuardar ;
V e n t a n a P r i n c i p a l : : f sGu ard arO K ( ) {
−>s e t _ t e x t ( f s G u a r d a r −>g e t _ f i l e n a m e ( ) ) ; −>h i d e ( ) ;
entrySalida
fsGuardar }
void
V e n t a n a P r i n c i p a l : : fsGuardarCANCEL ( ) {
fsGuardar
−>h i d e ( )
;
}
void
true
V e n t a n a P r i n c i p a l : : modoComprimir ( ) {
accionComprimir
=
;
true
−> s e t _ s e n s i t i v e ( metodo == MIO) ; e n t r y S a l i d a −> s e t _ s e n s i t i v e ( ) ; e n t r y S a l i d a −>s e t _ t e x t ( e n t r y E n t r a d a −>g e t _ t e x t ( )
parametro
+
" . cca " ) ;
+
extension ) ;
}
void
false
V e n t a n a P r i n c i p a l : : modoDescomprimir ( ) {
accionComprimir
=
;
false
−> s e t _ s e n s i t i v e ( ) ; e n t r y S a l i d a −> s e t _ s e n s i t i v e ( metodo
parametro
switch case break case break string
== MIO) ;
extension ;
( metodo ) {
MIO :
extension
=
" . dca " ;
=
" . y" ;
;
DNAX:
extension ;
}
entrySalida
−>s e t _ t e x t ( e n t r y E n t r a d a −>g e t _ t e x t ( )
}
void
new
V e n t a n a P r i n c i p a l : : ayudar ( ) {
true
∗ dialogoAyuda = D i a l o g ( " A c e r c a d e CODESEBI" , ) ; −>s e t _ h a s _ s e p a r a t o r ( ) ; d i a l o g o A y u d a −>g e t _ a c t i o n _ a r e a ( )−>s e t _ l a y o u t (BUTTONBOX_SPREAD) ; d i a l o g o A y u d a −>a d d _ b u t t o n ( S t o c k : : OK, RESPONSE_NONE) ; Dialog
dialogoAyuda
Image
i m a g e n ( " i m a g e n e s / adn . j p g " ) ;
Label
a p l i c a c i o n ( "CODESEBI
Label
a u t o r ( " Pablo
Label
f e c h a ( " 2006 " ) ;
dialogoAyuda dialogoAyuda
Urcola
v1 . 0 " ) ; Irache ") ;
−>g e t _ v b o x ( )−>add ( i m a g e n ) ; −>g e t _ v b o x ( )−>add ( a p l i c a c i o n ) ;
this ∗
,
this
,
A.30. PROGRAMA PRINCIPAL
109
−>g e t _ v b o x ( )−>add ( a u t o r ) ; −>g e t _ v b o x ( )−>add ( f e c h a ) ; d i a l o g o A y u d a −>s h o w _ a l l _ c h i l d r e n ( ) ; d i a l o g o A y u d a −>s e t _ d e f a u l t _ s i z e ( 2 5 0 , 1 0 0 ) ; d i a l o g o A y u d a −>r u n ( ) ; dialogoAyuda dialogoAyuda
}
delete
void
dialogoAyuda ;
V e n t a n a P r i n c i p a l : : usarMio ( ) {
metodo
= MIO ;
parametro
if
true
−> s e t _ s e n s i t i v e ( a c c i o n C o m p r i m i r ) ; −> s e t _ s e n s i t i v e ( ) ;
entryEntrada
( ! accionComprimir ) entrySalida
−>s e t _ t e x t ( e n t r y E n t r a d a −>g e t _ t e x t ( )
+
" . dca " ) ;
+
" . y" ) ;
}
void
V e n t a n a P r i n c i p a l : : usarDnax ( ) {
metodo
if
= DNAX;
parametro
−> s e t _ s e n s i t i v e (
( ! accionComprimir ) { entrySalida entrySalida
false false ) ;
−> s e t _ s e n s i t i v e ( ) ; −>s e t _ t e x t ( e n t r y E n t r a d a −>g e t _ t e x t ( )
} }
void if
VentanaPrincipal : : cargarConfiguracion () {
ifstream
conf ( " codesebi . conf " ) ;
( ! conf . f a i l () ) { string
linea ;
g e t l i n e ( conf ,
int if else
linea ) ;
conf . c l o s e () ; igual
=
l i n e a . f i n d ( '= ' ) ;
( igual
<
linea . size ()
&&
directorio . assign ( linea ,
directorio
else
=
igual
>=
i g u a l +1 ,
0) linea . size () ) ;
".";
}
directorio
=
".";
}
A.30. Programa principal #include #include using namespace int int
" v e n t a n a P r i n c i p a l . h"
main
Main
(
Gtk ;
argc ,
k i t ( argc ,
char
VentanaPrincipal
ventana ;
Main : : r u n ( v e n t a n a ) ;
}
return
0;
∗ argv
argv ) ;
[]) {
APÉNDICE A. CÓDIGO FUENTE DE LA IMPLEMENTACIÓN
110
A.31. Make le SHELL =
OBJ =
/ bin / sh
bstream . o
referencia .o
compresor . o
cola . o
excepcion . o
dialogo . o
OBJDNAX = costi .o
stampa . o
APP =
# #
CC =
basic00 . o
expand
adn . o
decodificador . o
−2. o
bit_base . o
rangos . o
bitio .o
fingerprint .o
arn . o
automata . o
ventanaPrincipal . o
fp . o
cerca_primo . o hash . o
main . o
coder . o
huffman . o
model
statistiche .o
codesebi
g++
−g −O3 − f o m i t −f r a m e − p o i n t e r −W −W a l l −DDEBUG=0 −O3 += −g −O3 − f o m i t −f r a m e − p o i n t e r −DDEBUG=0 −W −W a l l += $ ( s h e l l pkg− c o n f i g gtkmm − 2 . 4 −− c f l a g s ) += $ ( s h e l l pkg− c o n f i g s i g c ++−2.0 −− c f l a g s )
CFLAGS +=
CFLAGS +=
CXXFLAGS CXXFLAGS CXXFLAGS
−c o n f i g −c o n f i g
LIBS += $ ( s h e l l
pkg
LIBS += $ ( s h e l l
pkg
all :
gtkmm
− 2 . 4 −− l i b s ) −2.0 −− l i b s )
s i g c ++
$ (APP)
$ (APP) : $ (CXX)
$ ( OBJ)
$ (OBJDNAX)
$ (OPCIONES)
−o
$ (APP)
$ ( OBJ)
clean : $ (RM)
$ (APP)
$ ( OBJ)
$ (OBJDNAX)
$ (OBJDNAX)
$ ( LIBS )
codificador . o
\
descompresor . o
codici . o
−2. o
comp
\
−2. o \
r i c e r c a . o\