summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua')
-rw-r--r--Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua184
1 files changed, 92 insertions, 92 deletions
diff --git a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua
index ef40f0ee60d..d2b64270796 100644
--- a/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua
+++ b/Master/texmf-dist/tex/generic/pgf/graphdrawing/lua/pgf/gd/phylogenetics/BalancedMinimumEvolution.lua
@@ -34,44 +34,44 @@ declare {
algorithm = BalancedMinimumEvolution,
phase = "phylogenetic tree generation",
- summary = [["
- The BME (Balanced Minimum Evolution) algorithm tries to minimize
- the total tree length.
+ summary = [["
+ The BME (Balanced Minimum Evolution) algorithm tries to minimize
+ the total tree length.
"]],
documentation = [["
- This algorithm is from Desper and Gascuel, \emph{Fast and
- Accurate Phylogeny Reconstruction Algorithms Based on the
- Minimum-Evolution Principle}, 2002. The tree is built in a way
- that minimizes the total tree length. The leaves are inserted
- into the tree one after another, creating new edges and new
- nodes. After every insertion the distance matrix has to be
- updated.
+ This algorithm is from Desper and Gascuel, \emph{Fast and
+ Accurate Phylogeny Reconstruction Algorithms Based on the
+ Minimum-Evolution Principle}, 2002. The tree is built in a way
+ that minimizes the total tree length. The leaves are inserted
+ into the tree one after another, creating new edges and new
+ nodes. After every insertion the distance matrix has to be
+ updated.
"]],
examples = [["
- \tikz \graph [phylogenetic tree layout,
- balanced minimum evolution,
- grow'=right, sibling distance=0pt,
- distance matrix={
- 0 4 9 9 9 9 9
- 4 0 9 9 9 9 9
- 9 9 0 2 7 7 7
- 9 9 2 0 7 7 7
- 9 9 7 7 0 3 5
- 9 9 7 7 3 0 5
- 9 9 7 7 5 5 0}]
- { a, b, c, d, e, f, g };
+ \tikz \graph [phylogenetic tree layout,
+ balanced minimum evolution,
+ grow'=right, sibling distance=0pt,
+ distance matrix={
+ 0 4 9 9 9 9 9
+ 4 0 9 9 9 9 9
+ 9 9 0 2 7 7 7
+ 9 9 2 0 7 7 7
+ 9 9 7 7 0 3 5
+ 9 9 7 7 3 0 5
+ 9 9 7 7 5 5 0}]
+ { a, b, c, d, e, f, g };
"]]
}
-
-
-
-
+
+
+
+
function BalancedMinimumEvolution:run()
-
+
self.tree = Digraph.new(self.main_algorithm.digraph)
-
+
self.distances = Storage.newTableStorage()
-
+
local vertices = self.tree.vertices
-- Sanity checks:
@@ -79,25 +79,25 @@ function BalancedMinimumEvolution:run()
self.tree:connect(vertices[1],vertices[2])
return self.tree
elseif #vertices > 2 then
-
+
-- Setup storages:
self.is_leaf = Storage.new()
-
+
-- First, build the initial distance matrix:
local matrix = DistanceMatrix.graphDistanceMatrix(self.tree)
-
+
-- Store distance information in the distance fields of the storages:
for _,u in ipairs(vertices) do
for _,v in ipairs(vertices) do
self.distances[u][v] = matrix[u][v]
end
end
-
+
-- Run BME
self:runBME()
-- Run postoptimizations
- local optimization_class = self.tree.options.algorithm_phases['phylogenetic tree optimization']
+ local optimization_class = self.tree.options.algorithm_phases['phylogenetic tree optimization']
optimization_class.new {
main_algorithm = self.main_algorithm,
tree = self.tree,
@@ -106,11 +106,11 @@ function BalancedMinimumEvolution:run()
is_leaf = self.is_leaf,
}:run()
end
-
- -- Finish
+
+ -- Finish
self:computeFinalLengths()
self:createFinalEdges()
-
+
return self.tree
end
@@ -119,8 +119,8 @@ end
-- the BME (Balanced Minimum Evolution) algorithm
-- [DESPER and GASCUEL: Fast and Accurate Phylogeny Reconstruction
--- Algorithms Based on the Minimum-Evolution Principle, 2002]
---
+-- Algorithms Based on the Minimum-Evolution Principle, 2002]
+--
-- The tree is built in a way that minimizes the total tree length.
-- The leaves are inserted into the tree one after another, creating new edges and new nodes.
-- After every insertion the distance matrix has to be updated.
@@ -129,14 +129,14 @@ function BalancedMinimumEvolution:runBME()
local leaves = {}
local is_leaf = self.is_leaf
local distances = self.distances
-
+
-- get user input
for i, vertex in ipairs (g.vertices) do
leaves[i] = vertex
is_leaf[vertex] = true
end
- -- create the new node which will be connected to the first three leaves
+ -- create the new node which will be connected to the first three leaves
local new_node = InterfaceToAlgorithms.createVertex(
self.main_algorithm,
{
@@ -147,12 +147,12 @@ function BalancedMinimumEvolution:runBME()
g:add {new_node}
-- set the distances of new_node to subtrees
local distance_1_2 = self:distance(leaves[1],leaves[2])
- local distance_1_3 = self:distance(leaves[1],leaves[3])
- local distance_2_3 = self:distance(leaves[2],leaves[3])
+ local distance_1_3 = self:distance(leaves[1],leaves[3])
+ local distance_2_3 = self:distance(leaves[2],leaves[3])
distances[new_node][leaves[1]] = 0.5*(distance_1_2 + distance_1_3)
- distances[new_node][leaves[2]] = 0.5*(distance_1_2 + distance_2_3)
- distances[new_node][leaves[3]] = 0.5*(distance_1_3 + distance_2_3)
-
+ distances[new_node][leaves[2]] = 0.5*(distance_1_2 + distance_2_3)
+ distances[new_node][leaves[3]] = 0.5*(distance_1_3 + distance_2_3)
+
--connect the first three leaves to the new node
for i = 1,3 do
g:connect(new_node, leaves[i])
@@ -166,7 +166,7 @@ function BalancedMinimumEvolution:runBME()
-- note that the function called stores the k_dists before they are overwritten
self:computeAverageDistancesToAllSubtreesForK(g.vertices[i], { }, k,k_dists)
end
-
+
-- find the best insertion point
local best_arc = self:findBestEdge(g.vertices[1],nil,k_dists)
local head = best_arc.head
@@ -175,8 +175,8 @@ function BalancedMinimumEvolution:runBME()
-- remove the old arc
g:disconnect(tail, head)
g:disconnect(head, tail)
-
- -- create the new node
+
+ -- create the new node
local new_node = InterfaceToAlgorithms.createVertex(
self.main_algorithm,
{
@@ -187,28 +187,28 @@ function BalancedMinimumEvolution:runBME()
}
)
g:add{new_node}
-
+
-- gather the vertices that will be connected to the new node...
local vertices_to_connect = { head, tail, leaves[k] }
-
+
-- ...and connect them
for _, vertex in pairs (vertices_to_connect) do
g:connect(new_node, vertex)
g:connect(vertex, new_node)
end
-
+
if not is_leaf[tail] then
- distances[leaves[k]][tail] = k_dists[head][tail]
+ distances[leaves[k]][tail] = k_dists[head][tail]
end
if not is_leaf[head] then
- distances[leaves[k]][head] = k_dists[tail][head]
+ distances[leaves[k]][head] = k_dists[tail][head]
end
-- insert distances from k to subtrees into actual matrix...
self:setAccurateDistancesForK(new_node,nil,k,k_dists,leaves)
-
+
-- set the distance from k to the new node, which was created by inserting k into the graph
- distances[leaves[k]][new_node] = 0.5*( self:distance(leaves[k], head) + self:distance(leaves[k],tail))
-
+ distances[leaves[k]][new_node] = 0.5*( self:distance(leaves[k], head) + self:distance(leaves[k],tail))
+
-- update the average distances
local values = {}
values.s = head -- s--u is the arc into which k has been inserted
@@ -218,9 +218,9 @@ function BalancedMinimumEvolution:runBME()
end
end
---
+--
-- Updates the average distances from k to all subtrees
---
+--
-- @param vertex The starting point of the recursion
-- @param values The values needed for the recursion
-- - s, u The nodes which span the edge into which k has been
@@ -228,27 +228,27 @@ end
-- - new_node The new_node which has been created to insert k
-- - l (l-1) is the number of edges between the
-- new_node and the current subtree Y
---
+--
-- values.new_node, values.u and values.s must be set
-- the depth first search must begin at the new node, thus vertex
--- must be set to the newly created node
+-- must be set to the newly created node
function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leaves)
local g = self.tree
local leaf_k = leaves[k]
local y, z, x
if not values.visited then
values.visited = {}
- values.visited[leaf_k] = leaf_k -- we don't want to visit k!
+ values.visited[leaf_k] = leaf_k -- we don't want to visit k!
end
-- there are (l-1) edges between new_node and y
if not values.l then values.l = 1 end
if not values.new_node then values.new_node = g:outgoing(leaf_k)[1].head end
--values.s and values.u must be set
-
+
-- the two nodes which connect the edge on which k was inserted: s,u
local new_node = values.new_node
- local l = values.l
+ local l = values.l
local visited = values.visited
visited[vertex] = vertex
@@ -258,7 +258,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
local l = values.l
local y1= values.y1
- -- calculate distance between Y{k} and X
+ -- calculate distance between Y{k} and X
local old_distance -- the distance between Y{/k} and X needed for calculating the new distance
if y == new_node then -- this y didn't exist in the former tree; so use y1 (see below)
old_distance = self:distance(x,y1)
@@ -269,7 +269,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
local new_distance = old_distance + math.pow(2,-l) * ( self:distance(leaf_k,x) - self:distance(x,y1) )
self.distances[x][y] = new_distance
self.distances[y][x] = new_distance -- symmetric matrix
-
+
values.x_visited[x] = x
--go deeper to next x
for _, x_arc in ipairs (self.tree:outgoing(x)) do
@@ -292,7 +292,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
else
assert(values.y1,"no y1 set!")
end
-
+
z = arc.head -- root of the subtree we're looking at
y = arc.tail -- the root of the subtree-complement of Z
@@ -300,7 +300,7 @@ function BalancedMinimumEvolution:updateAverageDistances(vertex, values, k, leav
values.x_visited = {}
values.x_visited[y] = y -- we don't want to go there, as we want to stay within Z
loop_over_x( z,y, values ) -- visit all possible subtrees of Z
-
+
-- go to next Z
values.l = values.l+1 -- moving further away from the new_node
self:updateAverageDistances(z,values,k,leaves)
@@ -321,18 +321,18 @@ end
-- stored
-- - outgoing_arcs The table containing the outgoing arcs
-- of the current vertex
---
+--
-- @return The average distance of the new node #k to any subtree
-- The distances are stored as follows:
-- example: distances[center][a]
-- center is any vertex, thus if center is an inner vertex
--- it has 3 neighbors a,b and c, which can all be seen as the
+-- it has 3 neighbours a,b and c, which can all be seen as the
-- roots of subtrees A,B,C.
-- distances[center][a] gives us the distance of the new
-- node k to the subtree A.
--- if center is a leaf, it has only one neighbor, which
+-- if center is a leaf, it has only one neighbour, which
-- can also be seen as the root of the subtree T\{center}
---
+--
function BalancedMinimumEvolution:computeAverageDistancesToAllSubtreesForK(vertex, values, k, k_dists)
local is_leaf = self.is_leaf
local arcs = self.tree.arcs
@@ -340,13 +340,13 @@ function BalancedMinimumEvolution:computeAverageDistancesToAllSubtreesForK(verte
local center_vertex = vertex
-- for every vertex a table is created, in which the distances to all
-- its subtrees will be stored
-
+
values.outgoing_arcs = values.outgoing_arcs or self.tree:outgoing(center_vertex)
for _, arc in ipairs (values.outgoing_arcs) do
local root = arc.head -- this vertex can be seen as the root of a subtree
if is_leaf[root] then -- we know the distance of k to the leaf!
k_dists[center_vertex][root] = self:distance(vertices[k], root)
- else -- to compute the distance we need the root's neighboring vertices, which we can access by its outgoing arcs
+ else -- to compute the distance we need the root's neighbouring vertices, which we can access by its outgoing arcs
local arc1, arc2
local arc_back -- the arc we came from
for _, next_arc in ipairs (self.tree:outgoing(root)) do
@@ -356,25 +356,25 @@ function BalancedMinimumEvolution:computeAverageDistancesToAllSubtreesForK(verte
else
arc_back = next_arc
end
- end
-
+ end
+
values.outgoing_arcs = { arc1, arc2, arc_back }
-- go deeper, if the distances for the next center node haven't been set yet
- if not (k_dists[root][arc1.head] and k_dists[root][arc2.head]) then
+ if not (k_dists[root][arc1.head] and k_dists[root][arc2.head]) then
self:computeAverageDistancesToAllSubtreesForK(root, values, k,k_dists)
end
-
+
-- set the distance between k and subtree
- k_dists[center_vertex][root] = 1/2 * (k_dists[root][arc1.head] + k_dists[root][arc2.head])
- end
+ k_dists[center_vertex][root] = 1/2 * (k_dists[root][arc1.head] + k_dists[root][arc2.head])
+ end
end
end
--
-- Sets the distances from k to subtrees
--- In computeAverageDistancesToAllSubtreesForK the distances to ALL possible
+-- In computeAverageDistancesToAllSubtreesForK the distances to ALL possbile
-- subtrees are computed. Once k is inserted many of those subtrees don't
-- exist for k, as k is now part of them. In this function all
-- still accurate subtrees and their distances to k are
@@ -386,7 +386,7 @@ end
function BalancedMinimumEvolution:setAccurateDistancesForK(center,visited,k,k_dists,leaves)
local visited = visited or {}
local distances = self.distances
-
+
visited[center] = center
local outgoings = self.tree:outgoing(center)
for _,arc in ipairs (outgoings) do
@@ -395,11 +395,11 @@ function BalancedMinimumEvolution:setAccurateDistancesForK(center,visited,k,k_di
local distance
-- set the distance
if not distances[leaves[k]][vertex] and k_dists[center] then
- distance = k_dists[center][vertex] -- use previously calculated distance
+ distance = k_dists[center][vertex] -- use previously calculated distance
distances[leaves[k]][vertex] = distance
distances[vertex][leaves[k]] = distance
end
- -- go deeper
+ -- go deeper
if not visited[vertex] then
self:setAccurateDistancesForK(vertex,visited,k,k_dists,leaves)
end
@@ -419,7 +419,7 @@ end
-- - visited: The vertices that already have been visited
-- - tree_length: The current tree_length
-- - best_arc: The current best_arc, such that the tree
--- length is minimized
+-- length is minimzed
-- - min_length: The smallest tree_length found so far
function BalancedMinimumEvolution:findBestEdge(vertex, values, k_dists)
local arcs = self.tree.arcs
@@ -437,9 +437,9 @@ function BalancedMinimumEvolution:findBestEdge(vertex, values, k_dists)
c = arc.head --last visited arc
end
end
-
+
for i, arc in ipairs (unvisited_arcs) do
- local change_in_tree_length = 0
+ local change_in_tree_length = 0
-- set tree length to 0 for first insertion arc
if not values.tree_length then
values.tree_length = 0
@@ -456,15 +456,15 @@ function BalancedMinimumEvolution:findBestEdge(vertex, values, k_dists)
values.tree_length = values.tree_length + change_in_tree_length
end
-- if the tree length becomes shorter, this is the new best arc
- -- for the insertion of leaf k
+ -- for the insertion of leaf k
if values.tree_length < values.min_length then
values.best_arc = arc
values.min_length = values.tree_length
end
-
+
-- go deeper
self:findBestEdge(arc.head, values, k_dists)
-
+
values.tree_length = values.tree_length - change_in_tree_length
end
return values.best_arc
@@ -527,7 +527,7 @@ function BalancedMinimumEvolution:distance(a, b)
else
local distances = self.distances
return distances[a][b] or distances[b][a]
- end
+ end
end
@@ -543,7 +543,7 @@ function BalancedMinimumEvolution:computeFinalLengths()
for _, arc in ipairs(g.arcs) do
local head = arc.head
local tail = arc.tail
- local distance
+ local distance
local a,b,c,d
-- assert, that the length hasn't already been computed for this arc
if not lengths[head][tail] then