Mostrando las entradas con la etiqueta programación. Mostrar todas las entradas
Mostrando las entradas con la etiqueta programación. Mostrar todas las entradas

viernes, octubre 23, 2009

Macros de TNT: Variables (2)


En la pasada entrega (hace como mil años :P) escribí sobre como declarar las variables en los macros de TNT, en el post de hoy, voy a mostrar lo verdaderamente importante de las variables: su acceso.

Las variables se pueden acceder de dos maneras, una es la lectura, en donde el valor guardado en la variable es leído de alguna manera. La segunda forma de acceso es la escritura, en donde se asigna un valor a una variable.

Variables generales

En TNT para leer a las variables generales (las declaradas con la palabra clave var) se utiliza el nombre de la variable entre comillas simples (').
quote El valor de la variable es 'valor' ;
hold 'numero' ;
En este ejemplo, se imprime el número contenido en la variable valor. Y se retienen solo la cantidad de árboles que indica numero. Esta cualidad es muy importante, porque podemos reemplazar los parámetros de cualquier comando de TNT por variables, lo que le da una flexibilidad enorme a los macros.

A veces, en especial en la versión de linux, es necesario usar un paréntesis para que se lea correctamente la variable:
hold ('numero') ;
Para acceder a los arreglos, se utiliza el mismo formato, con el indice entre paréntesis cuadrados ([])
quote valor del elemento 4 del arreglo es 'arreglo [4]' ;
Es posible ser un poco más complejo es este caso
quote valor del elemento 'i' del arreglo es 'arreglo ['i']' ;
En este caso, se muestra el valor del elemento i dentro del arreglo. Véase que i va dentro de comillas. Para los que estén familiarizados con los lenguajes de programación pueden ver que al acceder a el valor de una variables este se "dereferencia" con las comillas.

Este es el ejemplo con arreglos multidimencionales
quote valor del elemento 'i', 'j' es 'dosd ['i', 'j' ]' ;
El indice del arreglo puede ser una operación entre paréntesis típicos (()), el ejemplo va con un array de dos dimensiones, pero es igualmente valido para arreglos de cualquier dimensión.
quote valor del elemento 4, 'j' es 'dosd [ (2 + 2), 'j' ] ;
Otra posibilidad muy útil en arreglos es el uso se series
quote el valor de los elementos 3 al 8 son 'lista [ 3 - 8 ];
En este caso es importante ¡no colocar los valores entre paréntesis! De lo contrario TNT interpreta una operación matemática.

Para escribir variables en TNT se utiliza la palabra clave set, usando el nombre de la variable a asignar, sin comillas, y seguida del valor asignado.
set valor 4 ;                   /* Asigna 4 a valor */
set resultado (3 + 4) ; /* Asigna una operación */
set numero 'valor' ; /* Asigna el contenido de valor a numero */
Véase que cuando lo que se asigna es el valor dentro de una variable, esta debe ir entre comillas. Para asignar arreglos se puede utilizar el mismo formato, asignando un elemento a la vez
set arreglo [4] 5 ;             /* Asigna 5 al elemento 4 del arreglo */
set arreglo [ (2 + 3) ] 8 ; /* Asigna 8 al elemento 5 del arreglo */
set arreglo ['i'] 10 ; /* Asigna 10 al i-elemento de arreglo */
set arreglo [ ('j' + 'k') ] 7 ; /* Asigna 7 al elemento j + k del arreglo */
Es importante anotar que los indices del arreglo deben dereferenciarse!

Muchas veces, las operaciones sobre las variables consisten en modificar su valor, por ejemplo, incrementar su valor en 1.
set valor 'valor' + 1 ;
Es mucho más claro e intuitivo, modificar directamente la variable sin dereferenciarla, esto se logra mediante operadores que usan una sintaxis como la de C en esos casos.
set valor ++ ;                 /* incrementa valor en 1 */
set arreglo [3] -- ; /* disminuye el contenido del elemento 3 de arreglo en 1 */
set matriz [2, 4] += 'valor' ; /* adiciona el contenido de valor al elemento 2, 4 de matriz */
set numero *= (3 + 'j') ; /* multiplica el contenido de numero por 3 más j */
set arreglo [2] /= 3 ; /* divide el contenido de arreglo en 3 */
set valor -= 4 ; /* disminuye el contenido de valor en 4 */
Para los arreglos puede ser más útil asignar a la vez todos los elementos, para ello se utiliza setarray. Es muy importante que las dimensiones del arreglo coincidan con las de su declaración. El formato de set array es las dimensiones del arreglo, seguido por el nombre del arreglo, seguido por los elementos.
var:
lista [5, 4]
;

setarray 5, 4 lista 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 2 2 2 2 ;
En este ejemplo se creo un array de 5 x 4 que tiene la siguiente matriz
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
2 2 2 2
El orden de los elementos es siguiendo el orden de las dimensiones de izquierda a derecha, así en el ejemplo los primeros 4 elementos son los elementos [0, 0], [0, 1], [0, 2], y [0, 3] del arreglo.

Variables en ciclos

En general, las variables de los ciclos son de control, y por ello, lo mejor es no modificarlas. Así en principio, las variables de los ciclos son de solo lectura. Si se necesita modificar el valor de la variable de un ciclo, TNT también puede hacerlo, aunque es importante recalcar que las modificaciones de las variables en un ciclo, suelen reflejar algún problema de diseño, y no es una buena practica recurrir a esas modificaciones.

Las variables de ciclos se pueden leer usando nombres o números. Es una buena practica el utilizar nombres para identificar las variables de los ciclos.

Para leer una variable de un ciclo se utiliza el número del ciclo antecedido por el carácter numeral (#). Por ejemplo, para recorrer varios valores de k usando pesos implicados [1]
loop =kval 1 10
keep 0 ;
piwe = #kval ;
mult ;
tsave* resu#kval.tre ; save; tsave /;
stop
El #kval se refiere al primer ciclo, también podría utlizarse #1, en ese caso, para guardar el arbol debería usarse
tsave* resu#1..tre
Véase que al guardar el nombre del árbol se usa un doble punto despues del número. Eso es porque con un solo punto, TNT interpreta que forma parte del número (es decir, que se trata de un real con decimales). De todas formas, mejor utilizar el nombre ;). Los números de los ciclos se asignan de acuerdo a su anidamiento (empezando desde #1).

Para modificar el valor de una variable de un ciclo se utiliza la palabra clave setloop, que modifica el ciclo más anidado en el que se encuentra la instrucción. Dado que el cambiar el valor de los ciclos distorsiona la secuencia del ciclo, hay que tener cuidado con los ciclos infinitos. Es por eso que su uso no es recomendable. Sin embargo, a veces necesitamos de un ciclo que corra indefinidamente hasta que se cumpla alguna condición. En ese caso, utilizar setloop junto a endloop puede ser muy útil. Por ejemplo
var:
i
;

set i 0 ;
loop =non 0 1
/* varias instrucciones */
if ('i' == 1)
endloop ;
else
setloop 0 ;
end ;
stop
Aquí se asume que en alguna condición dentro del ciclo el valor de i se cambia a 1, lo que permite que el ciclo finalice.

Variables de linea de comando

Las variables que vienen desde la linea de comando son de solo lectura. Así solo podemos accesar su valor. Para acceder al valor de una variable de linea de comando se usa el signo (%)
set i %1 ;
asigna a i el valor del primer parámetro pasado por la linea de comando (por interés %0 es el nombre del macro). Tratar de leer más parámetros de los que se pasaron por linea de comando, es un error, y detiene la ejecución. A la hora de escribir un macro, hay que tener en cuenta que son estos parámetros de la línea de comando la única manera de comunicarse con el usuario, así que hay que hacer una buena elección de su orden, y de los valores por omisión.

Como siempre, no se olviden de chequear que su versión de TNT esta actualizada, así mismo no duden en consultar la wiki de TNT o suscribirse al grupo google de TNT!

Referencias
[1] Goloboff, P.A. 1993. Estimating character weights during tree search. Cladistics 9: 83-91. DOI: 10.1111/j.1096-0031.1993.tb00209.x

Post anteriores en macros de TNT

lunes, julio 13, 2009

Macros de TNT: Variables (1)


En el post anterior olvide algo muy importante. Se trata de los comentarios.

El lenguaje de macros de TNT permite el uso de comentarios en la misma forma que el tradicional C, es decir entre un /* y un */. Los comentarios no tienen ningún efecto sobre el script, pero son muy útiles para documentar el código.

/* Este es un comentario */

Es muy importante colocar comentarios, no solo para que otras personas puedan entender el código, sino para que uno mismo pueda entenderlo más rápidamente cuando vuelve a el (en especial, si fue escrito hace tiempo!).

Los comentarios son validos, una vez se a iniciado el modo de macros (usando macro=)

Por tradición, coloco este macro simple

macro =;
/* Mi primer macro de TNT */

quote Hola mundo!;
p/;

Ahora entrando en materia con el tema de este post...


Las variables son los objetos que el programa manipula con un propósito especificado por el usuario. Las variables guardan valores, y estos valores pueden ser modificados o leídos. Muchas veces, es el valor contenido en una variable lo que nos interesa. En otras ocasiones, el contenido de una variable sirve para controlar el flujo del programa. También pueden usarse variables para guardar valores dados por el usuario.

Al arrancar un macro, TNT define por omisión un número de variables (1000). Estas se pueden acceder usando un número, que inicia desde 0. Es posible cambiar el numero de variables usando macro* N K; donde N es el número de loops, y K el número de variables.

Variables generales

Usar los números de las variables puede ser cómodo en ,macros pequeños, pero al incrementar la complejidad de los macros, se hace más difícil el mantenimiento del código, por lo que es una buena práctica usar nombres para las variables. Las variables se pueden nombrar en cualquier parte del programa. Pero es una buena práctica nombrarlas justo después de iniciar el archivo con el macro (después del macro=). Para su declaración se utiliza la palabra clave var.

Hay dos formas de nombrar las variables, una es una forma explicita, que sirve, más que todo, para mantener la compatibilidad con macros anteriores.

var =
0 variable1
1 variable2
5 variable3
;

En este formato, usando var= se tiene que nombrar cada variable con el número interno (de TNT) que la identifica. La declaración termina con un punto y coma. El principal problema con esta forma, es que invita al uso intercambiable de números y nombres en las variables. Eso puede tener un efecto nosivo a la hora de hacer mantenimiento al código (por ejemplo, querer agregar más variables).

Una forma mucho más cómoda, y más recomendable (evita el uso de variables sin nombre), es declarar directamente los nombres, usando dos punto (:) en vez de igual

var:
variable 1
variable 2
variable 3
;

De aquí en adelante, utilizo esta forma, que me parece, mejora la legibilidad del código escrito.

Las variables en TNT pueden ser simples, es decir, que contienen un solo valor, o pueden ser arreglos, series de valores consecutivos. Los arreglos de TNT son estáticos, es decir que no pueden redimensionarse en tiempo de ejecución. Por eso es bueno declararlos solo cuando ya sabemos el tamaño que puede tener. Por ejemplo, luego de leer los datos, ya sabemos cuantos nodos puede tener un árbol.

Declarar un arreglo es muy simple, es como una variable normal, pero con las dimensiones entre corchetes ([]), si es una matriz multidimensional, los valores se separan con comas (,) de forma similar a como se declaran los arreglos en pascal.

var:
arreglo [25]
matriz [3, 4]
;


Variables en ciclos

En TNT las variables de los ciclos son independientes de las variables generales. Estas variables son manejadas por TNT y no directamente por el usuario. Al igual que las variables tradicionales, pueden nombrarse, o usar los números que vienen por omisión que comienzan desde 1, y se incrementan al irse anidando los ciclos.

Yo en general utilizo los números. Quizá sea una mejor práctica utilizar nombres puesto que de esa manera se independiza de el anidamiento del ciclo, y además, es la única forma de acceder variables de ciclos desde otro archivo.

La forma de declarar una variable en un ciclo es anteponiendo un igual (=) antes del nombre:

loop =ciclo 1 10


Variables de linea de comando

Al llamar a un macro, es posible asignarle valores iniciales usando la línea de comandos asociada al llamado del macro. Estas variables se conocen como "argumentos" o "parámetros". Por ejemplo, uno podría tener un macro que se llame dojac, y que reciba como parámetros el número de replicas, y un número de iteraciones en cada replica, así

dojac 1000 20 ;

En este caso, se reciben 1000 replicas y cada replica tiene 20 iteraciones.

En general, cuando uno distribuye un macro, si no se da ningún parámetro, se ofrece una especie de salida de ayuda, donde explica el objetivo y las condiciones necesarias para utilizar el macro de forma correcta.

La función argnumber retorna el número de argumentos usados al invocar el macro.

No se olviden de revisar las novedades de TNT, y por supuesto, consultar la wiki de TNT ;), hay varios scripts y otra documentación muy útil :D

viernes, mayo 15, 2009

Algoritmos en filogenia 0b: Árboles


Otro de los componentes básicos de un programa de análisis filogenético son los árboles. Los árboles pueden ser el resultado del análisis (como en los programas de análisis cladístico), o pueden ser parte de los datos usados (como en los programas de análisis biogeográfico).

Los árboles, son además, una de las estructuras de datos más conocidas y usadas en programación. En programación un árbol es una colección de elementos (nodos), los nodos están relacionados entre sí por un "parentesco" que les impone una jerarquía. El parentesco es una relación de pares: un nodo es el ancestro y el otro es el descendiente. Un nodo puede tener un número indefinido de descendientes, más como máximo solo puede tener un ancestro.

En general, en filogenía se llama nodo, únicamente a los elementos que poseen descendientes, y hojas o terminales, a los elementos sin descendientes (en ciencias de computadores se utiliza más nodo interno y nodo terminal o nodo hoja, aquí yo sigo la notación de ciencias de computadores, y utilizo nodos cuando me refiero a todos los elementos del árbol).

Un árbol tiene como máximo un nodo raíz, que es un nodo interno sin ancestro. A diferencia de los árboles más abstractos de ciencias de computadores, los únicos elementos con datos incluidos por el usuario son los terminales (que entran vía la matriz de datos). Los datos guardados por los nodos internos son inferidos mediante algún algoritmo.

Existen varias formas de representar un árbol. Para mi, la más natural es usando estructuras y apuntadores. He aquí un nodo básico
typedef struct tagPHYLONODE PHYLONODE;

struct tagPHYLONODE {
PHYLONODE* anc;
PHYLONODE* left;
PHYLONODE* right;
STATES* recons;
};
Esta estructura es el nodo de un árbol binario, es decir, que cada nodo interno tiene dos descendientes, los apuntadores left, y right, que como pueden notar apuntan a elementos del tipo PHYLONODE. anc es el puntero a el ancestro. En esta estructura el nodo raíz tiene a anc como NULL (es decir que no apunta a ningún elemento), y los nodos terminales tienen left y right como NULL. recons es un arreglo con los caracteres (en forma de campo de bits).

Yo suelo guardar la información del terminal (extraída de la matriz de datos) en una estructura aparte, por ejemplo
typedef struct tagTERMINAL TERMINAL;
struct tagTERMINAL {
char name [32];
STATES* chars;
};
E incluyo un apuntador a TERMINAL como parte de PHYLONODE
struct tagPHYLONODE {
... //Otros campos aquí
TERMINAL* term;
};
Si es un nodo interno, term es NULL.

Una de las ventajas de los árboles es que un subárbol tiene las mismas propiedades de un árbol, por lo que los algoritmos recursivos son muy naturales al trabajarlos con árboles. Aún así, yo prefiero tener siempre una estructura que guarda el árbol
typedef struct tagPHYLOTREE PHYLOTREE;
struct tagPHYLOTREE {
unsigned numNodes;
PHYLONODE* root;
PHYLONODE* nodeArray;
DATAMATRIX* matrix;
};
En esta estructura se guarda un puntero al nodo raíz (root), un array con los nodos del árbol (nodeArray), un apuntador a la matriz de datos (matrix) y el número de nodos.

Esta aproximación tiene la ventaja de que uno bien puede tener varios conjuntos de árboles de forma independiente, por ejemplo, cada árbol con su propio id, o nombre, que no es una característica del nodo raíz, sino del conjunto completo de los nodos.

Aparte de las estructuras es posible guardar los árboles como arrays coordinados. Esta opción, por ejemplo, es usada en [1] para el código que aparece en los ejemplos, y también es la manera de manejar los árboles en el lenguaje de macros de TNT (que no maneja estructuras). La declaración de los arreglos coordinados es más sencilla
int* anc;
int* left;
int* right;
STATES** chars;
En este caso anc, left y right son arreglos dinámicos (por eso están declarados como apuntadores, pero se pueden tratar como arrays), y en vez de contener un apuntador, contienen un numero que es el índice del array. Como es un arreglo coordinado, todos los elementos con el mismo índice son parte del mismo nodo. Así, por ejemplo anc [17] = 20; dice que el ancestro del nodo 17, es el nodo 20. En este caso left [20] o right [20] debe ser igual a 17. chars [20] contiene los estados asignados al nodo 20. Si revisan las entradas sobre árboles en wikipedia (en especial las entradas sobre heaps) notaran que esa es la manera con la que tratan los árboles.

Para mi, lo malo de esa aproximación, es que requiere un control más fuerte sobre el mantenimiento de la información (cabe anotar que en el lenguaje de macros TNT, TNT mantiene todo por nosotros, así que eso no es ningún problema!). En mi propia experiencia, yo trabaje en reconciliación de árboles, y trabajaba con alguien que no sabia manejar apuntadores. Así que trate de hacer la implementación con arreglos coordinados. pero en árboles reconciliados no siempre sabemos cuantos nodos nuevos va a tener el árbol, por lo que mantener el código con los arreglos coordinados se hizo bien problemático.

Lo que muestra esa experiencia, no es que una alternativa es mejor que la otra, solo que a veces, la naturaleza del problema puede complicar la forma de resolverlo, y que además algunos estilos de programación se dan mejor que otros, según quien este haciendo el código ;). De aquí en adelante en otros posts, yo voy a usar estructuras.

Para tener algo de código y resaltar la recursividad de los árboles he aquí una función que guarda un árbol en formato parentética (como Hennig86, NONA y TNT)
#include < stdio.h >

void PrintTree (FILE* out, PHYLOTREE* tree) {
fprintf (out, "tread \'Simple tree output\'\n");
PrintNode (out, tree - > root)
fprintf (out, ";\np/;");
}

void PrintNode (FILE* out, PHYLONODE* node) {

if (node - > term != NULL) {
fprinf ("%s ", node - > term - > name);
return;
}
fprintf (out, "(");
PrintNode (out, node - > left);
PrintNode (out, node- > right);
fprintf (out, ") ");
}
Estas funciones usas las operaciones IO estándar. La función PrintTree coloca la cabecera de un archivo de árboles para Hennig86/NONA/TNT. Y llama a PrintNode. PrintNode chequea si el nodo actual es un terminal, si es así escribe el nombre del terminal, de lo contrario, como en un nodo interno, imprime los paréntesis y llama recirsivamente a PrintNode en cada uno de sus descendientes.

Me parece que Mike Keesey escribió un post sobre árboles bajo programación orientada a objetos, pero no pude encontrarlo, esta es la alternativa más parecida :P

Referencias
[1] Goloboff, P. A. 1997. Self weighted optimization: tree searches and character state reconstruction under implied transformation costs. Cladistics 13: 225-245. doi: 10.1111/j.1096-0031.1997.tb00317.x


Post anteriores en Algoritmos en filogenia
0a. Campos de bits

miércoles, mayo 06, 2009

Macros de TNT: Intro


Una de las utilidades más poderosas de TNT es su lenguaje de macros. Este lenguaje permite acceder variables internas de TNT, manipular árboles y datos. Esto en conjunto con el poder de computo de TNT es una excelente combinación.

Infortunadamente, bien sea porque no hay un manual extenso, o porque aún son pocos los que han usado explicitamente macros en sus artículos, esta utilidad suele pasar más o menos desapercibida para los usuarios. En esta serie de posts quiero dar un poco de remedio a esta situación, y dar una especie de introducción a las muchas posibilidades que permite el uso de macros.

Parte de la idea nació a que una vez vi el libro de "R para filogenia" [1], y pues a que he estado en contacto con Santi Catalano, que ha estado trabajando en la wiki de TNT. Espero poder postear después parte de esto a la wiki de TNT, pero por ahora, como para ver como me siento escribiendolo, lo coloco primero en mi blog ;).

El estilo, es bien orientado a la programación--mi influencia más poderosa es Kernighan y Ritchie :)--pues la idea es que se le saque el máximo provecho al lenguaje!

Notación

El lenguaje de macros de TNT es un lenguaje interpretado, esto quiere decir que cada instrucción se ejecuta a medida que se va leyendo, por lo que es posible ir "escribiendo" el programa en tiempo real desde la linea de comando.

Esto puede ser muy útil, por ejemplo, para realizar cálculos matemáticos directamente en TNT.

Por ejemplo:
> macro = ;
Macro language is ON
> var: dest ;
> set dest 4 + 5 ;
> quote 'dest' ;
9
Al escribir esa secuencia uno puede tener una calculadora simple. Esto sirve para introducirnos a las cosas particulares del lenguaje.

Para activar los macros, se usa el comando macro = ; con macro - ; se desactivan los macros.

Al terminar cada instrucción se coloca un punto y coma (;). Aunque no es necesario, por claridad es aconsejable dejar un espacio antes del punto y coma.

La palabra clave var se utiliza para declarar las variables.

Con la palabra clave set se asigna un valor a una variable. En este ejemplo el valor de una suma. Set acepta las cuatro operaciones básicas, así como operaciones más complejas usando paréntesis.

El comando quote imprime en pantalla. En TNT, para acceder al valor guardado en las variables, se coloca el nombre de la variable entre comillas simples. Así en este ejemplo, se imprime lo que esta dentro de dest.

Es importante diferenciar entre el valor guardado en la variable y su nombre. Set asigna a una variable, por ello la variable no va dentro de comillas, pero si lo que es asignado es otra variable, entonces como es un valor, debe estar entre comillas:
set dest 'primero' * 'segundo' ;
Esta instrucción asigna a dest la multiplicación de los valores de primero y segundo.

Sin embargo, la aplicación más importante de los macros de TNT es que pueden guardarse en un archivo y ejecutarse como si se tratara de un comando del programa.

Si los macros se guardan con la extensión ".run", y son colocados en el mismo directorio de trabajo del programa (por ejemplo c:\bin\tnt) es posible llamarlo simplemente usando el nombre del archivo. Por ejemplo, en la instalación de TNT esta incluido stats.run, que calcula el indice de consistencia y retención de los árboles en memoria. Para ejecutarlo, simplemente se escribe
> stats ;
en la linea de comando, y el macro es ejecutado automáticamente.

Como todos los archivos de TNT se pueden acceder usando el comando proc, pero se pierde la lista de parámetros (si los hay) del macro. Por eso es mejor usar el commando run (o simplemente escribir el nombre). Como cualquier comando se puede acceder directamente en la lista de parámetros del programa.

Como ejercicios de esta introducción se puede probar las diferentes maneras de invocar los macros, así como acceder valores desde comandos. Por ejemplo scripts como este:
macro = ;
var:
numIts
numTrees
itTrees;

set numIts 100 ;
set itTrees 10 ;
set numTrees 'numIts' * 'itTrees' ;

rseed 0;
hold 'numTrees' ;
mult = replic 'numIts' hold 'itTrees' ;
nel * ;
p/ ;
Que no hacen nada que no se puede hacer directamente (y segura más fácil!), pero sirven para familiarizarse con el lenguaje ;).

Referencias
[1] Paradis, E. 2006. Analysis of phylogenetics and evolution with R. Springer

viernes, abril 24, 2009

Algoritmos en filogenia 0a: Campos de bits


Intro

Quiero iniciar una serie de posts sobre los algoritmos usados en análisis filogenético. El motivo principal fue ver el árticulo sobre “filogenética computacional” (y los tópicos de sistemática) en wikipedia, que pues me parecen algo sesgados hacía los métodos basados en modelos, y en general los algoritmos de filogenia no están muy representados.

Hay un par de ejemplos muy buenos en i-net de algoritmos de filogenia, uno es el libro de Wheeler et al. [1], y en una vena similar, un manuscrito de DeLaet [2]. Sin embargo, los algoritmos que presentan son más bien generales, lo cual es muy bueno desde el punto de vista didáctico, pero en varios casos, alejado de lo que hacen los programas en la actualidad!

Como esas fuentes son muy buenas, espero enfocarme más en el aspecto de la implementación de los algoritmos. La idea es pasar de los más sencillos a los más complejos (en la medida en la que yo pueda comprenderlos xD).

Antes de empezar, pues quiero agradecer a Pablo Goloboff, que siempre ha estado dispuesto a discutir de algoritmos conmigo :). Por supuesto, los errores que tengan mis implementaciones son mis errores!

A medida que avance, iré posteando el código fuente en google code o sourceforge, por si desean examinarlo, requiere que sepan algo de C. El HTML tiene problemas con los símbolos mayor-que y menor-que, por los que los mostrare en estos posts como texto, en vez de usar el símbolo. Gracias a Rubén por el tip del HTML :)!

Campos de bits

Un componente básico del análisis filogenéticos son los caracteres. Asumamos que solo tenemos un carácter para cada terminal. Uno bien podría guardar cada estado en una variable, por ejemplo asignandole 0, 1, 2... según corresponda. Una idea así esta implícita en la descripción inicial del “groundpland divergence” de Wagner [3], y más o menos, en la formalización de Farris [4, ver 5]. Las operaciones entre caracteres serían operaciones de intervalos. Pero es mucho más sencillo ver a los caracteres como un conjunto de estados [4, 6]. Las operaciones entre caracteres serian operaciones de conjuntos. Esos conjuntos tienen además una característica particular: son perfectamente booleanos, es decir, un taxon tiene o no un determinado estado. Esto tiene dos consecuencias positivas: (i) podemos guardar el conjunto de estados como un campo de bits; (ii) las operaciones entre caracteres son operaciones de los campos de bits.

Las compus guardan los datos como números binarios. En un campo de bits, usamos esa particularidad para representar conjuntos de bits. Un ejemplo, aclara mejor la situación:
Estado    Representación binaria    "Número" (humano)
0 0001 1
1 0010 2
2 0100 4
3 1000 8
0, 1 0011 3
1, 3 0101 5
Como se ve, cada estado individual tiene su propio bit, y la combinación de estados es simplemente la unión los estados. Muchos lenguajes de programación incorporan operaciones para trabajar directamente con bits (not, and, or y xor) con lo cual la traducción de operaciones de conjuntos a operaciones de bits es directa.

En esta serie voy a utilizar un char para guardar los estados de carácter. En C, char es de 8 bits. Yo lo defino con un typedef, de manera que después es posible cambiar el número de bits en el bitfield.
#define BITS_ON_STATE 8
#define ALL_BITS_ON 255
typedef char STATES;
En este pequeño ejemplo, se leen los caractes de un taxon, desde un archivo (in), y se guardan en un array de caracteres (chars). El número de caracteres es nc, y se usan las funciones getc para leer caracteres de texto, SkipSpaces para ignorar los espacios de texto, y isdigit para reconocer si el carácter de texto es un número.
for (j = 0; j < nc; ++ j) {
error = SkipSpaces (in);
if (error != NO_ERROR) return error;
c = getc (in);
if (isdigit (c))
chars [j] = 1 < < (c - '0');
else if ((c == '?') || (c == '-'))
chars [j] = ALL_BITS_ON;
else return BAD_FORMAT;
}
En la operación chars [j] = 1 < < (c – '0') se resta el valor ASCII de '0' (30) al valor ASCII guardado en c (es un número, va de 30 a 39). El valor de esa resta lo usamos para correr los bits de 1. Así por ejemplo, si se lee un '0', la operación seria:
chars [j] = 1 < < (30 – 30)
chars [j] = 1 < < 0
[0000 0001 < < 0 = 0000 0001]
chars [j] = 1
Si leemos un 5
chars [j] = 1 < < (35 – 30)
chars [j] = 1 < < 5
[0000 0001 < < 5 = 0010 0000]
chars [j] = 32
Corrimos el 1 cinco bits a la izquierda.

Observen que los no aplicables o desconocidos, se codifican con todos los bits encendidos.

Esto funciona bastante bien para caracteres no aditivos. Para caracteres aditivos, es posible "recodificarlos" como varios caracteres binarios [7][8], una vez recodificados es posible utilizarlos como si fueran caracteres no aditivos independientes.

Hay formas más sofisticas de usar los campos de bits, uniendo varios caracteres en una sola variable (por ejemplo, en una variable de 32 bits, se pueden usar 8 caracteres de 4 bits, como nucleotidos) [8][9]. Ese empaquetado permite una evaluación muchisimo más rápida de los caracteres durante las búsquedas, puesto que en cada operación se pueden revisar simultáneamente varios caracteres.

Referencias
[1] Wheeler, W. et al. 2006. Dynamic homology and phylogenetic systematics: a unified approach using POY. American Mus. of Natural History, published in cooperation with NASA. online: http://research.amnh.org/scicomp/pdfs/wheeler/Wheeler_etal2006b.pdf
[2] DeLaet, J. 2005. Pseudocode for some tree search algorithms in phylogenetics. Manuscrito online: http://www.plantsystematics.org/publications/jdelaet./algora.pdf
[3] Wagner, W.H. 1961. Problems in the classification of ferns. En: Recent advances in botany. Toronto Univ. Press. pp. 841-844.
[4] Farris, J.S. 1970. Methods for computing Wagner trees. Syst. Zool. 19: 83-92.
[5] Goloboff, P.A. et al. 2006. Continuos characters analyzed as such. Cladistics 22: 589-601. doi: 10.1111/j.1096-0031.2006.00122.x
[6] Fitch, W.M. 1971. Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool. 20: 406-416.
[7] Farris, J.S. et al. 1970. A numerical approach to phylogenetic systematics. Syst. Zool. 19: 172-189.
[8] Moilanen, A. 1999. Searching for most parsimonious trees with simulated evolutionary optimization. Cladistics 15: 39-50. doi: 10.1111/j.1096-0031.1999.tb00393.x
[9] Goloboff, P.A. 2002. Optimization of polytomies: state and parallel set operations. Mol Phyl. Evol. 22: 269-275. doi: 10.1006/mpev.2001.1049

miércoles, noviembre 12, 2008

Core coding

En estos días, algunas de las ideas que tengo de mi proyecto, no están saliendo como yo quería, así que me he dedicado a la programación de algunos detalles computacionales... como el asunto, aunque muy relacionado con computadoras, pero poco con cladística (aparte claro, de ser parte de mi proy xD).. lo deje en mi blog personal :P.

English version:

How can Java (and several other languages) programmers live without pointers?

lunes, abril 14, 2008

C--

Bueno, el post esta más relacionado con la programación que con la biogeografía... pero si les interesa, ahí puse algunas de mis experiencias recientes con el C++...