In silico methods for genome rearrangement analysis : from identification of common markers to ancestral reconstruction.

De
Publié par

Sous la direction de Serge Dulucq, Macha Nikolski
Thèse soutenue le 09 décembre 2008: Bordeaux 1
L'augmentation du nombre de génomes totalement séquencés rend de plus en plus efficace l'étude des mécanismes évolutifs à partir de la comparaison de génomes contemporains. L'un des principaux problèmes réside dans la reconstruction d'architectures de génomes ancestraux plausibles afin d'apporter des hypothèses à la fois sur l'histoire des génomes existants et sur les mécanismes de leur formation. Toutes les méthodes de reconstruction ancestrale ne convergent pas nécessairement vers les mêmes résultats mais sont toutes basées sur les trois mêmes étapes : l'identification des marqueurs communs dans les génomes contemporains, la construction de cartes comparatives des génomes, et la réconciliation de ces cartes en utilisant le critère de parcimonie maximum. La qualité importante des données à analyser nécessite l'automatisation des traitements et résoudre ces problèmes représente de formidables challenges computationnels. Affiner le modèles et outils mathématiques existants par l'ajout de contraintes biologiques fortes rend les hypothèses établies biologiquement plus réalistes. Dans cette thèse, nous proposons une nouvelle méthode permettant d'identifier des marqueurs communs pour des espèces évolutivement distantes. Ensuite, nous appliquons sur les cartes comparatives reconstituées une nouvelle méthode pour la reconstruction d'architectures ancestrales basée sur les adjacences entre les marqueurs calculés et les distances génomiques entre les génomes contemporains. Enfin, après avoir corrigé l'algorithme existant permettant de déterminer une séquence optimale de réarrangements qui se sont produits durant l'évolution des génomes existants depuis leur ancêtre commun, nous proposons un nouvel outil appelé VIRAGE qui permet la visualisation animée des scénarios de réarrangements entre les espèces
-Génome ancestral
-Génomique comparative
-Réarrangement
-Point de cassure
-Permutation
Abstract
-Ancestral genome
-Comparative genomics
-Rearrangements
-Breakpoints
-Permutation
Source: http://www.theses.fr/2008BOR13704/document
Publié le : mardi 25 octobre 2011
Lecture(s) : 70
Nombre de pages : 158
Voir plus Voir moins

.
AIGLE
.
Co-directrice
.
d'ordre
.
:
.
3704
.
THÈSE
Professeur
PRÉSENTÉE
.
À
TIN
L'UNIVERSITÉ
Professeur
BORDEA
Chargée
UX
.
I
.
ÉCOLE
.
DOCTORALE
.
DE
orteur
MA
.
THÉMA
.
TIQUES
.
ET
Examinateur
D'INF
.
ORMA

TIQUE
2008
P
.
ar
Professeur
Géraldine
.
JEAN
.
POUR
Alain
OBTENIR
.
LE
.
GRADE
.
DE
.
DOCTEUR
DULUCQ
SPÉCIALITÉ
Professeur
:
.
INF
.
ORMA
Guillaume
TIQUE
.
In
.

.
metho
MELANCON
ds
.
for
.
genome
.
rearrangemen
NIKOLSKI
t

analysis:
he
from
.
iden
.
tication
.
of
.

.
mark
.
ers
.
to
.

Examinateur

DENISE
Souten
.
ue
.
le
.
:
.
9
.

.
bre
.
2008
Rapp
Après
Serge
a
.
vis
.
des
.
rapp
.
orteurs
.
:
.
Bernard
.
MORET

.
FER
.
Professeur
Professeur
.
Alain
.
DENISE
.
.
.
.
.
.
Guy
.
.
Professeur
.
Dev
.
an
.
t
.
la
.

Examinateur
d'examen
ha

.
osée
de
de
herc
:

hel
oNun
souten
Jean-Mic
ts
ëon
A
des
v
l'INRIA,
an
la
t
grand
tout,
toujours
je
tan
tiens

à
hes.
remercier
à
très
elopp
sincèremen
soutien
t
ses
Serge
est

la
sans
une
qui
de
je
Isab
n'aurais
un
jamais
aidée
osé
et
me
oratoire
lancer
Beyne
dans
Loira

ses
longue
our
a
de
v
le
en

ture.
t
Je
une
v
dans
ous
ec
remercie
remerciemen
de

m'a
e
v
t
oir
Alexandre
fait
our

En-
la
le
bioinformatique,
Roubineau
je
iii
v
à
ous
qui
remercie
supp
égalemen
:
t
Ca
de
v
m'a
oulanger
v
qui
oir
Ha
transmis
tions,
le

virus
Am
de
longues
la
Renault

son
herc
toine
he
mes
et
our
merci
pâtisseries
enn
à
d'a
au
v

oir
à

diciles
de
thèse
dev
partager
enir
notions
mon
t

ensée
de

thèse
Merci
malgré
départemen
un
1
emploi
Billaud,
du
k
temps
Journet,
plus
Eric
que
et

leur
hargé.
os
Je
n'oublie
v
du
ous
e
suis
hez,
plus
tes
que


égalemen
te
mes
p
du
our
t
v
écoutée
otre
au
disp
en
onibilité
p
et
Iragne,
v
Emman
os
ses
précieux
pratiques

de
Je
après-midi,
tiens
v
à
pu
remercier
mon
égalemen
Soueidan
t
etites
très
drien

ses
haleureusemen
Ouangraoua
t
amitié,

et
ha
t
Nik
de
olski
Da
qui
our
a
professionnel

p
de
olley-ball,

p
ma
duran
thèse.
étitions

surtout
ha,
goût
je
our
te
Un
remercie
sp
d'a
Martin
v
en
oir
du
été
et
présen
qui
te
ue,

v
haque
momen
jour
t
duran
de
t
a
ma
j'ai
thèse,
plus
d'a
et
v
biologie...
oir
ne
guidé

mes
etite

tous
herc
j'ai
hes
er
a
qu'enseignan
v
toute
ec
édagogique
bien
in-
v
de

plus
et

de
hel
m'a
Lépine,
v
Mon
oir

toujours
Ly

Dutour
quand
ena
je
gen
ne
en
trouv
de
ais
v
pas
à
forcémen
a
t
plaisir.
de
non
rép
ersonnel
onses
et
à
particulier
mes
Cath
questions.
Marie
Mes
m'on
remerciemen
de
ts
et
v
mes
on
herc
t
Merci
égalemen
t
t
tous
aux

professeurs
amis
Bernard
LaBRI
Moret
m'on
et
toujours
Alain
ue,
Denise
et
qui
ortée
m'on
lab
t
ou
fait
dehors
l'honneur
je
de
ense
rapp
Florian
orter
Cyril
mon
yla,
man
uelle

et
de
tra
thèse.
aux
Je
sur
remercie
levure
tout
b
autan

t


a
hel
ec
Aigle,
j'ai
Guy
dév
Melancon
er
et
anglo-hispanique,
Guillaume
yssam
F
et
ertin
p
p
atten
our
A
a
Go
v
et
oir
précieux

Aïda
de
p
lire
son
mon
Maxime
tra
blard
v
son
ail
duran
et
nos
p
préparations
our
TD
a
graphes,
v
vid
oir
p
été
son
présen

ts
et
le
amour
jour
our
J
v
p
An
our
Rollet
faire
our
partie

de
t
mon
rép
jury
de
de
et
thèse.
p
Je
notre
remercie

aussi
p
l'ensem
les
ble
tunisiennes.
des
remerciemen

tout
de
écial
l'équip
Tiphaine
e
qui
MA
dev
GNOME
ue
dans
l
laquelle
temps
j'ai
amie
grandi
une
duran
te,
t
m'a

souten
trois
aidée
années
a
:

merci
les
à
ts
Da
notammen
vid
à
Sherman
n
p
ma
our
et
m'a
v
v
qui
oir
pu
donné
bien

que
opp
théorèmes
ortunité,
des
à
de
P
Mes

ts
Durrens
seraien
p
pas
our
sans
ses
p
explications
p
p
à
édagogiques
les

que
t
pu
le
y
monde
en

t
de
te.
la
à
biologie
l'équip
!
p
Je
du
souhaite
t
égalemen
formatique
t
l'IUT
remercier
Bordeaux
les
et
biologistes
particulièremen
du
à
pro
hel
jet

Génolevures
Marcus,
notammen
hel
t

Jean-Luc
aël
Souciet
tassier,
et
Pinlou,
Bernard
holas
Dujon
Olivier
qui
,
on
elle
t
et
pris
Sop
le
p
temps
leur
de
tillesse
m'expliquer
leur
leurs
vie
problématiques
tagieuse
et
partager
de
sa
s'in
oir.
téresser
seigner
à
v
mon

tra
été
v
réel
ail.
Je
Notre
pas

plus
oration
p
a
administratif
largemen
LaBRI
t
de

en
tribué
Philipp
à
Biais,
ma
y

et
de
Sanc
la
qui
génomique
t
et
à
à
main
faire
reprises
a
qui
v
Remerciemen
de
tin
a
t
paren
toujours
me
eu
iv
un
de
mot
mon
gen
de
til
de
p
plus
our
Bordeaux
moi.
b
En
mes
dehors
de
du

lab
merci
oratoire,
mots
je
ts
tiens

à

remercier
baisser
viv
mon
emen
p
t
Je
les
t
p
remercie
ersonnes
famille.
qui
v
m'on
et
t
d'in

s'il
née
je
tout
hère
au
toujours
long
me
de
moral
ma
souhaite
thèse
uel,
en
duran
me
T
p
y
ermettan
toi,
t
des
de
lors

ée
tin
our
uer
de
ma
ma
passion,
toutes
la
qui
GRS.
en
Je
amies.
remercie
évidemmen
du
et
fond
à
du
de

jamais
eur
en
la
v
GR
b
de
à
Sain
hes
t
parfois
Pierre

Mon
Un
tlimart
ma
et
eur,
la
qui
Laëtitia
é
de
p
Nan
er
tes
ter
(Ev
les
elyne,
Enn,
Aude,
mon
P
bre.
auline,
as
P
haque


Hélène,
en
Gaëlle,
as
Elise,
moi,
Maud,

Marion,
moi.
Bérangère,
sans
Nancy
bras
,
Alors
Anne-F

rance)
de
p
arriv
our
à
les
p
éc
me
hanges
ermettre
sp

ortifs
uer
et
passion.
les
remercie
momen

ts
ordelaises
passés
son
ensem
dev
ble
ues
malgré
vraies
la
Je

bien
Je
t
remercie
amis
égalemen
ma
t
Merci
la
mes

ts
fédérale
n'a
GRS
oir
de

la

FSCF
moi
(Annic
d'a
k,
oir

tré
hel,
eaucoup
Cathie,
térêt

mes
Corinne,
herc
Céline,
même
Anne-
était
Marie,
dicile


Martine)
que
qui
faisais.
m'a
immense
p
à
ermis

de
so
m'in
femme
v
lettres,
estir
a
dans
trouv
mon
les
sp
justes
ort
our
tout
motiv
en
et

remon
t
le
professionnellemen
dans
t.
momen
Enn,
diciles.
je
je
remercie
remercier
la
homme

l'om
GR
Emman
de
tu
l'Union
été
Sain

t
jour
Bruno
t
(Elo
longue
die
v
D.,
ture.
Elo
u
die
toujours
B.,
en
Rémédios,
tu
Aurélie,
as
Marion
parfois
et
que
toutes
Sans
mes
j'aurais
gymnastes)
doute
qui
les
m'a
bien
très
fois.
gen
merci.
timen
on
t
ymond
A
mes
et
grands-p
v
ères,
Ravies
dèles
des
Métho
nouv
des
temp
in
en

les
p
esp
our
les
l'étude
une
des
outil
réarrangemen
de
ts
jout
génomiques
réalistes.
:
tier
de
Ensuite,
l'iden
our
tication
les
de
l'algorithme
marqueurs
son


uns
la
à
génomique
la


existan

tes
L'augmen
établies
tation
nous
du
p
nom
uns
bre
emen
de
les
génomes
elle
totalemen

t
les

tre
rend
a
de
ermettan
plus
réarrangemen
en
duran
plus
ts

osons
l'étude
GE
des
scénarios

èces.
év
t,
olutifs
m
à
les
partir
outils
de
par
la


fortes
de
yp
génomes
t


temp
osons
orains.
métho
L'un
t
des
marqueurs
prin-
our

év
problèmes
distan
réside
appliquons
dans

la
une

de



basée
de
en
génomes


génomiques
plausibles
génomes
an
Enn,
d'app
oir
orter
t
des
de
h
optimale
yp
qui
othèses
pro
à
l'év
la
exis-
fois
leur
sur
nous
l'histoire
nouv
des
elé
génomes
p
existan
animée
ts
réarrangemen
et
les
sur
génome
les
e,

oin
ismes
p
de
vii
leur
Aner
formation.
mo
T
et
outes
mathématiques
les
ts
métho
l'a
des
de
de
train

biologiques

rend
ne
h

othèses
v
biologiquemen
ergen
plus
t
Dans
pas
thèse,

prop
t
une
v
elle
ers
de
les
ermettan
mêmes
d'iden
résultats
des
mais

son
p
t
des
toutes
èces
basées
olutiv
sur
t
les
tes.
trois
nous
mêmes
sur
étap

es
parativ
:

l'iden
nouv
tication
métho
de
p
marqueurs
la


un

dans
sur
les

génomes
tre

marqueurs
temp
et
orains,

la
en

les
de


orains.

après
es
v
des

génomes,
existan
et
p
la
t

déterminer
de


de

ts
en
se
utilisan
t
t
duits
le
t

olution
de
génomes
parcimonie
tan
maxim
depuis
um.

La
un,
quan
prop
tité
un
imp
el
ortan
app
te
VIRA
des
qui
données
ermet
à
visualisation
analyser
des

de
l'automatisation
ts
des
tre
traitemen
esp
ts
Mots-clés:
et

résoudre


réarrangemen
problèmes
p
représen
t
te

de
er-
formidables
utation

Résumé
hallengesy

scenarios
In


during
metho
great
ds
In
for
e
genome
after
rearrangemen
a
t
breakp
analysis:

from
yp
iden
new
tication
for
of
genome

w
mark
optimal
ers
from
to
p

ords:


The
Through

metho
in
relev
the
adding
n
e
um
the
b

er
t
of
metho
en

tirely


orary
genomes
algorithm
mak
ts
es
of

w


the
visualization
study
een
of
e
the
erm

needs
hanisms

of
t
ev
dels
olution
w
through
more
the
t

b
of


thesis,
temp
ose
orary
d
genomes.
tication
One
ers
of
e
the
olutionary
main
Next,
problems
a
is
of
to
based

syn
plausible
ers

b
genome


Finally

the
whic

h
of
furnishes
o
h
ev
yp
dern
otheses

ab
prop
out
to
b
GE
oth
the
the
rearrangemen
history
et
of
ecies.

genome,
temp
rearrangemen
orary
ts,
genomes
tion
and
these
the

general


hallenges.
hanisms
renemen
of
of
their
mo
formation.
and
While
ds,
not
e
all
obtain
metho
biologically
ds
an
for
h
the
otheses

y

biological

ts.

this
v
w
erge
prop
to
a
w
metho
ards
for
the
iden
same
of
results,
mark
they
to
are

all
maps
based
ev
on
distan
the
genomes.
same
w
three
apply
steps:
new
iden
d
tication

of


on
mark
of
ers
ten
in
mark

and
temp

orary
et
genomes,
een

temp
of
genomes.

,
e

maps
existing
for
for
these
an
genomes,

and
rearrangemen

that
of

these
the
maps
olution
under
mo
a
genomes
maxim
their
um

parsimon
e
y
ose

new
The
ol
quan
VIRA
tit
that
y
ermits
of
animated
data
of
that
t
m
b
ust
w
b
sp
e
Keyw
analyzed

requires

the

automation
ts,
of
oin
pro
p

uta-
and
viii
meet-
ing
.
.
ten
.
ts
.
List
.
of
.
Figures
.
xiii

List
.
of
mark
T
.
ables
.
xv
.
In
.
tro
random

.
1
25
I
.
Preliminaries
rearrangemen
7
.
1
Iden
Mo
.
deling
19
a
.
genome
.
and
.
ev
.
olutionary
.

.
hanisms
ragile
9
.
1.1
genomes
Common
.
mark
.
ers:
.
what
.
is
.
a
16
syn
.

.
blo
2

olution
k?
syn
.
.
.
.
.
.
.
y
.
.
.
.
.
.
.
2.1.2
.
.
.
.
.
.
.
.
.
metho
.
.
.
.
.
.
.
.
.
mo
9
mo
1.1.1
24

een
information
.
is
.

2.2.1
tained
genomes
in
.
the
.
genome
.
.
.
.
.
.
.
.
.
.
.
.
Multiple
.
problem
.
.
.
.
.
.
.
.
.
rom
.
to
10
19
1.1.2
of
Common
y
mark
.
ers
.
b
.
et
.
w
.
een
.
sp
Grimm-Syn
ecies
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
dHoRe
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.3
.
.
.
.
.
.
10
.
1.2
.

.
king
.
ev
.
olutionary
2.1.4

oin
hanisms
v
b
oin
y
.
op
.
erations
Ev
on
et
p
w
erm
.
utations
.
.
.
.
.
.
.
.
rev
.
unic
11
.
1.2.1
.
The
.
genome:
Con
a
.
signed
.
or
.
unsigned
.
p
.
erm
.
utation
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1.3.4
.
genome
.
t
.
.
.
.
.
.
.
.
11
.
1.2.2
.
Rearrangemen
.
ts:
.
dieren
18
t
F
p

ossible
ers
op
ev
erations
scenarios
.
2.1
.
tication
.
genome
.
ten
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
.
1.3
.
Mathematical
.
measure
2.1.1
of
ten
ev
.
olution
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
.
I-A
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
.
1.3.1
.
Rearrangemen
.
t
.

.
.
.
.
.
.
.
.
22
.
Other
.
ds
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
.
F
.
breakp
.
t
.
del
15
ersus
1.3.2
breakp
P
t
arsimonious
del
rearrangemen
.
t
.
scenario
.
.
2.2
.
olutionary
.
b
.
w
.
t
.
o
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24
.
The
.
ersal
16
for
1.3.3
hromosomal
Breakp
.
oin
.
ts
.
.
.
.
.
.
.
.
ix
.
.ts
4.1.1
.
2.2.2
.
Extension
.
to
.
m
.

Extension
hromosomal
of
genomes
.
.
.
.
4
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
.
2.2.3
genomes
Other
.

.
.
.
.
.
.
.
.
.
.
.
.
and
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Complexit
.
.
.
.
.
ersus
.
.
.
.
.
.
.
.
.
.
.
Discussion
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
oundaries
2.3
.
P
.
arsimonious
62
scenarios
.
.
.
.
.
.
.
.
b
.
.
.
63
.
new
.
.
.
.
.
blo
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
67
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
GRIMM-Syn
.
.
.
.
35
.
2.3.1
.
Computing
.
a
.
parsimonious
.
scenario
70
for
.
unic
.
hromosomal
.
genomes
.
.
.
.
.
.
.
35
.
2.3.2
Application
Computation
.
of
.
an
.
optimal
73
scenario
.
for
.
m
.

.
hromosomal
.
genomes
60
.
homologous
36
.
2.3.3
.
Wh
.
y
.
is
.
giving
.
only
Extended
one
.
optimal
.
scenario
.
misleading?
.
.
.
.
.
.
.
.
3.3.2
.
genes
.
.
.
.
.
.
.
.
.
A
42
ositioning
2.4
oundaries
Global
.
metho
.
ds
.
for
64

ten

ks
.
.
.
.
.
.
.
.
.
.
.
.
.
3.4.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Concatenation
.
.
.
.
.
.
43
.
2.4.1
.
Breakp
.
oin
.
t-based
68
metho
.
d
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
69
.
y
.
algorithm
.
.
.
.
.
.
.
.
.
.
.
east
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
Mammal
2.4.2
.
Rearrangemen
.
t-based
.
metho
.
d
.
.
.
.
.
.
71
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
72
.
y
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Contents
.
.
46
.
2.4.3
.
Other
.
w
.
orks
.
based
.
on
.
parsimon
.
y
.
.
.
.
3.3
.
of
.
b
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3.1
.
segmen
.
.
.
.
.
.
50
.
2.4.4
.

.
k
.
of
.
biological
.

.
ts
.
.
.
.
.
.
.
.
62
.
Groups
.
homologous
.
and
.
oundaries
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3.3
.
dding
.
p
.
of
.
b
.
.
.
.
.
.
51
.
2.5
.
Piece-wise
.

.
.
.
.
3.4
.
syn
.
y
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
65
.
Duplications
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
.
2.5.1
.
Metho
.
d
.
from
.
ph
.
ylogenetic
.
data
3.4.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.5
.
y
.
.
.
.
.
.
51
.
2.5.2
.
Ph
.
ylogen
.
y
.
vs
.
ev
.
olution
.

.
hanisms
.
.
.
.
.
.
.
.
.
.
.
.
68
.
Applications
.
4.1
.
ten
.
v
.
SyDiG
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
55
.
I
.
I
69
SyDiG:
Y

results
v
.
ering
.
Syn
.
ten
.
y
.
in
.
Distan
.
t
.
Genomes
.
57
.
3
.
SyDiG
.
algorithm
.
59
.
3.1
.
Pre-pro
.

4.1.2
.
results
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.1.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.2
59
to
3.2
east
Syn
.
ten
.
y
.
graph
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
.
.

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.