Diferencia entre revisiones de «Reconstrucción filogenética»
De Lógica computacional y teoría de modelos (2019-20)
(Página creada con «<source lang = "prolog"> </source>») |
|||
Línea 1: | Línea 1: | ||
<source lang = "prolog"> | <source lang = "prolog"> | ||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % Problema 1: Reconstrucción filogenética. | ||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % Ulises Pastor Díaz. | ||
+ | % Lógica computacional. | ||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % | ||
+ | % Descripción del problema: Dado un conjunto de unidades taxonómicas, un | ||
+ | % conjunto de caractéres, su dominio y sus expresiones en dichas | ||
+ | % unidades taxonómicas, queremos construir el árbol filogenético que | ||
+ | % maximice la compatibilidad de los caractéres dados. | ||
+ | % | ||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % | ||
+ | %% Parte 1: Construcción del árbol binario enraizado. 2n-1 será la raiz | ||
+ | %% y 1..n las hojas. Las aristas serán decrecientes. | ||
+ | % | ||
+ | % Número de hojas. | ||
+ | |||
+ | numT(N) :- N = #count{L : taxa(L)}. | ||
+ | |||
+ | % Etiquetado de hojas. | ||
+ | |||
+ | leaf(1..N) :- numT(N). | ||
+ | |||
+ | % Etiquetado de nodos. | ||
+ | |||
+ | node(1..2*N-1) :- numT(N). | ||
+ | |||
+ | % Cada nodo interior tiene dos hijos (generación). | ||
+ | |||
+ | 2{edge(I,J) : node(J)}2 :- node(I), not leaf(I). | ||
+ | |||
+ | % Los hijos tienen menor índice para que las aristas sean decrecientes. (CASO IGUAL). | ||
+ | |||
+ | :- node(I;J), edge(I,J), I <= J. | ||
+ | |||
+ | % Cada nodo, salvo la raiz tiene un antecesor. | ||
+ | |||
+ | 1 {edge(I,J) : node(I)} 1 :- node(J), numT(N), J < 2*N-1. | ||
+ | |||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % | ||
+ | %% Parte 2: Construcción de la función en los nodos internos. | ||
+ | % | ||
+ | %% Definición de h: | ||
+ | % | ||
+ | % h es una función total. | ||
+ | |||
+ | 1 {h(I,C,V) : dom(C,V)} 1 :- node(I), char(C). | ||
+ | |||
+ | % h es una extensión de f. | ||
+ | |||
+ | h(I,C,V) :- leaf(I), f(I,C,V). | ||
+ | |||
+ | %% Compatibilidad: | ||
+ | % | ||
+ | % Extraemos las aristas asociadas a cada característica. | ||
+ | |||
+ | c_edge(C,V,A,B) :- node(A;B), | ||
+ | dom(C,V), | ||
+ | edge(A,B), | ||
+ | h(A,C,V), | ||
+ | h(B,C,V). | ||
+ | |||
+ | % Dividimos los nodos en cada nuevo subárbol en raíces y nodos internos. | ||
+ | |||
+ | nroot(C,V,A) :- node(A;B), | ||
+ | dom(C,V), | ||
+ | h(A,C,V), | ||
+ | c_edge(C,V,B,A). | ||
+ | |||
+ | root(C,V,A) :- node(A), | ||
+ | dom(C,V), | ||
+ | h(A,C,V), | ||
+ | not nroot(C,V,A). | ||
+ | |||
+ | % Indentificamos los valores para los que el subgrafo tiene más de una raiz. | ||
+ | |||
+ | two_roots(C,V) :- node(A;B), | ||
+ | A < B, | ||
+ | dom(C,V), | ||
+ | root(C,V,A), | ||
+ | root(C,V,B). | ||
+ | |||
+ | % Definimos la compatibilidad parcial. | ||
+ | |||
+ | par_compatible(C,V) :- dom(C,V), not two_roots(C,V). | ||
+ | |||
+ | % Definimos la compatibilidad. (Probar otra def) | ||
+ | |||
+ | -compatible(C) :- char(C), dom(C,V), not par_compatible(C,V). | ||
+ | |||
+ | compatible(C) :- not -compatible(C), char(C). | ||
+ | |||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % | ||
+ | %% Parte 3: Presentación. | ||
+ | |||
+ | #show h/3. | ||
+ | #show compatible/1. | ||
+ | #show edge/2. | ||
+ | #show com/1. | ||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % | ||
+ | %% Parte 4: Optimización. --opt-mode=optN | ||
+ | |||
+ | com(K) :- K = #count{C : compatible(C)}. | ||
+ | #maximize{1,C : compatible(C)}. | ||
+ | |||
+ | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
+ | % | ||
+ | %% Parte 5: Problema de decisión: | ||
+ | |||
+ | #const k = 1. | ||
+ | % :- com(K), K < k. | ||
+ | % k {compatible(C) : char(C)}. | ||
+ | |||
+ | |||
</source> | </source> |
Revisión actual del 11:41 18 feb 2019
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problema 1: Reconstrucción filogenética.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ulises Pastor Díaz.
% Lógica computacional.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Descripción del problema: Dado un conjunto de unidades taxonómicas, un
% conjunto de caractéres, su dominio y sus expresiones en dichas
% unidades taxonómicas, queremos construir el árbol filogenético que
% maximice la compatibilidad de los caractéres dados.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 1: Construcción del árbol binario enraizado. 2n-1 será la raiz
%% y 1..n las hojas. Las aristas serán decrecientes.
%
% Número de hojas.
numT(N) :- N = #count{L : taxa(L)}.
% Etiquetado de hojas.
leaf(1..N) :- numT(N).
% Etiquetado de nodos.
node(1..2*N-1) :- numT(N).
% Cada nodo interior tiene dos hijos (generación).
2{edge(I,J) : node(J)}2 :- node(I), not leaf(I).
% Los hijos tienen menor índice para que las aristas sean decrecientes. (CASO IGUAL).
:- node(I;J), edge(I,J), I <= J.
% Cada nodo, salvo la raiz tiene un antecesor.
1 {edge(I,J) : node(I)} 1 :- node(J), numT(N), J < 2*N-1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 2: Construcción de la función en los nodos internos.
%
%% Definición de h:
%
% h es una función total.
1 {h(I,C,V) : dom(C,V)} 1 :- node(I), char(C).
% h es una extensión de f.
h(I,C,V) :- leaf(I), f(I,C,V).
%% Compatibilidad:
%
% Extraemos las aristas asociadas a cada característica.
c_edge(C,V,A,B) :- node(A;B),
dom(C,V),
edge(A,B),
h(A,C,V),
h(B,C,V).
% Dividimos los nodos en cada nuevo subárbol en raíces y nodos internos.
nroot(C,V,A) :- node(A;B),
dom(C,V),
h(A,C,V),
c_edge(C,V,B,A).
root(C,V,A) :- node(A),
dom(C,V),
h(A,C,V),
not nroot(C,V,A).
% Indentificamos los valores para los que el subgrafo tiene más de una raiz.
two_roots(C,V) :- node(A;B),
A < B,
dom(C,V),
root(C,V,A),
root(C,V,B).
% Definimos la compatibilidad parcial.
par_compatible(C,V) :- dom(C,V), not two_roots(C,V).
% Definimos la compatibilidad. (Probar otra def)
-compatible(C) :- char(C), dom(C,V), not par_compatible(C,V).
compatible(C) :- not -compatible(C), char(C).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 3: Presentación.
#show h/3.
#show compatible/1.
#show edge/2.
#show com/1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 4: Optimización. --opt-mode=optN
com(K) :- K = #count{C : compatible(C)}.
#maximize{1,C : compatible(C)}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 5: Problema de decisión:
#const k = 1.
% :- com(K), K < k.
% k {compatible(C) : char(C)}.