From: Jean-François Couchot <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Fri, 8 Mar 2013 13:57:55 +0000 (+0100)
Subject: debut classe equivalence
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ancetre.git/commitdiff_plain/5e17bc6675db329838a7a6902e3956f16cfbbcf1?ds=inline;hp=--cc

debut classe equivalence
---

5e17bc6675db329838a7a6902e3956f16cfbbcf1
diff --git a/classEquiv.tex b/classEquiv.tex
new file mode 100644
index 0000000..5d9f19d
--- /dev/null
+++ b/classEquiv.tex
@@ -0,0 +1,46 @@
+This step considers as input the set 
+$\{((g_1,g_2),r_{12}), (g_1,g_3),r_{13}), (g_{n-1},g{n}),r_{n-1.n})\}$ of 
+$\frac{n(n-1)}{2}$ elements. 
+Each one $(g_i,g_j),r_{ij})$ where $i < j$, 
+is a pair that gives the similarity rate $r_{ij}$ between the genes  
+$g_{i}$ and $g_{j}$ in $G$.
+
+The first step of this stage consists in building the following non-oriented
+graph furthere denoted as to \emph{similarity graphe}.
+In this one, the vertices are the genes. There is an edge between 
+$g_{i}$ and $g_{j}$ if the rate $r_{ij}$ is greater than a given similarity 
+treeshold $t$.
+
+We then define the relation $\sim \in G \times G $ such that
+$ x \sim y$ if $x$ and $y$ belong in the same connected component.
+Mathematically speaking, it is obvious that this 
+defines an equivalence relation. 
+Let $\dot{x}= \{y \in G | x \sim y\}$
+denotes the equivalence class to which $x$ belongs.
+All the elements of $G$ which are  equivalent to each other
+are also elements of the same equivalence class.
+Let us then consider the set of all equivalence classes of $G$ 
+by $\sim$, denoted $X/\sim = \{\dot{x} | x \in G\}$. 
+We then consider the projection $\pi: G \to G/\mathord{\sim}$
+defined by \pi(x) = \dot{x} 
+which maps elements of $G$ into their respective equivalence classes by $\sim$.
+
+
+
+
+For each genome $G=[g_l,\ldot,g{l+m}]$, the second step computes 
+the projection of each gene according to $\pi$. 
+Let $G'$ the resulting genome  which is 
+$$
+G'=[\pi(g_l),\ldot,\pi(g{l+m})]
+$$ 
+is of size $m$.
+
+Intuitivelly speaking, for two genes $g_i$ and $g_j$ 
+in the same equivalence class, there is path from  $g_i$ and $g_j$.
+It signifies that  each evolution step 
+(represented by an edge in the similarity graph) 
+has produced a gene s.t. the similarity with the previous one 
+is greater than $t$. 
+Genes $g_i$ and $g_j$ may thus have a common ancestor.
+