1 This step considers as input the set
2 $\{((g_1,g_2),r_{12}), (g_1,g_3),r_{13}), (g_{n-1},g{n}),r_{n-1.n})\}$ of
3 $\frac{n(n-1)}{2}$ elements.
4 Each one $(g_i,g_j),r_{ij})$ where $i < j$,
5 is a pair that gives the similarity rate $r_{ij}$ between the genes
6 $g_{i}$ and $g_{j}$ in $G$.
8 The first step of this stage consists in building the following non-oriented
9 graph furthere denoted as to \emph{similarity graphe}.
10 In this one, the vertices are the genes. There is an edge between
11 $g_{i}$ and $g_{j}$ if the rate $r_{ij}$ is greater than a given similarity
14 We then define the relation $\sim \in G \times G $ such that
15 $ x \sim y$ if $x$ and $y$ belong in the same connected component.
16 Mathematically speaking, it is obvious that this
17 defines an equivalence relation.
18 Let $\dot{x}= \{y \in G | x \sim y\}$
19 denotes the equivalence class to which $x$ belongs.
20 All the elements of $G$ which are equivalent to each other
21 are also elements of the same equivalence class.
22 Let us then consider the set of all equivalence classes of $G$
23 by $\sim$, denoted $X/\sim = \{\dot{x} | x \in G\}$.
24 We then consider the projection $\pi: G \to G/\mathord{\sim}$
25 defined by \pi(x) = \dot{x}
26 which maps elements of $G$ into their respective equivalence classes by $\sim$.
31 For each genome $G=[g_l,\ldot,g{l+m}]$, the second step computes
32 the projection of each gene according to $\pi$.
33 Let $G'$ the resulting genome which is
35 G'=[\pi(g_l),\ldot,\pi(g{l+m})]
39 Intuitivelly speaking, for two genes $g_i$ and $g_j$
40 in the same equivalence class, there is path from $g_i$ and $g_j$.
41 It signifies that each evolution step
42 (represented by an edge in the similarity graph)
43 has produced a gene s.t. the similarity with the previous one
45 Genes $g_i$ and $g_j$ may thus have a common ancestor.
