Acciones

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)}.