[PDF] Combinatoire and Bio-informatique: Comparaison de structures d

View - Download Combinatoire and Bio-informatique: Comparaison de structures d

Previous PDF

Next PDF

ÉCOLEDOCTORALESTIM

Année2005

THÈSE

pourobtenirlegradede

DOCTEURDEL'UNIVERSITÉDENANTES

Discipline:Informatique

présentéeetsoutenuepubliquementpar

GuillaumeBLIN

le17novembre2005 devantlejuryci-dessous

Directeurdethèse:Pr.IrenaRUSU

Encadrantsdethèse:Pr.GuillaumeFERTIN

COMPARAISONDESTRUCTURESD'ARNETCALCULDE

DISTANCESINTERGÉNOMIQUES

comparisonandgenomicdistancecomputation

GuillaumeBLIN

UniversitédeNantes

GuillaumeBLIN

distancesintergénomiques xxi+170p. these-IRINestdisponibleàl'adresse:

Impression:these.tex-9/12/2005-20:06

Àpapietnanouquej'aimetoutautant

Àmabellefamilleadorée;o)

Etàzoé±monamour

-GuillaumeBLIN,

Remerciements

poursesnombreuxconseils. larégionparisienne.

Notesdelecture

nuscrit. j'aicollaboré.

LINA-FRECNRS2729UniversitédeNantes,

CédricCHAUVEDannyHERMELIN

CP8888,Succ.Centre-VilleMountCarmel,

RomeoRIZZIStéphaneVIALETTE

romeo.rizzi@unitn.itvialette@lri.fr

Sommaire

IConceptsgénéraux

ix

Introduction

recherche. enSection1.2). adaptésàleurétudealgorithmique. troistypesderésultats: xi xiiIntroduction plexité. -estunproblèmeNP-complet.

Introductionxiii

prouvantlaNP-complétudeduproblème. diversperspectivesetproblèmesouverts.

PARTIEI

Conceptsgénéraux

CHAPITRE1

Notionsdegénétique

reconnuqu'en1907. 3

4CHAPITRE1-Notionsdegénétique

ont,pourleurpart,montré: aminés

2.lemécanismedesmutations;

3.laprésenced'uncodedefindelecture.

1.rechercherdenouveauxgènes;

2.déterminerlafonctiondecesderniers;

CHAPITRE1-Notionsdegénétique5

génétique: toujourssurlesloisdeMendel; (ADNouARN)auseindelacellule;

Modifiés)dansdesorganismesvivants;

unedéficiencehéréditaire. centraldelabiologiemoléculaire.

1.2.1Lesgènes

6CHAPITRE1-Notionsdegénétique

1.2.2L'AcideDésoxyriboNucléique

ryotes

Figure1.3-Gèneetchromosome.

CHAPITRE1-Notionsdegénétique7

phosphate baseazotée. dusucreestrenomméeeni0pourtouti.

8CHAPITRE1-Notionsdegénétique

purines(l'Adénine).

CHAPITRE1-Notionsdegénétique9

1.2.3L'AcideRiboNucléique

10CHAPITRE1-Notionsdegénétique

l'ADN); molécules. illustréenFigure1.11. structurauxsuivants:

CHAPITRE1-Notionsdegénétique11

12CHAPITRE1-Notionsdegénétique

d'EscherichiaColi[60](vuepartielle).

1.2.4Lesprotéines

Figure1.14-Compositiond'unacideaminé.

CHAPITRE1-Notionsdegénétique13

êtreclasséeentroisniveaux:

turessecondaires: etformantunesortedefeuilletplissé. ensemblecompact. lafindelatranscription.

14CHAPITRE1-Notionsdegénétique

CHAPITRE1-Notionsdegénétique15

illustréenFigure1.19.

16CHAPITRE1-Notionsdegénétique

Figure1.19-Lecodegénétique.

CHAPITRE2

Complexitéet

algorithmique

Figure2.1-Muhammad

R tionfdonnée. P 17

18CHAPITRE2-Complexitéetalgorithmique

Exemple2.1.

LEVOYAGEURDECOMMERCE

trajett2T.

Démarrerenmonocycle

Entrée:Unmonocycle

Principe:

1.Seplacerderrièrelemonocycle

3.Placerlaselledansl'entre-jambe

4.Appuyersurlapédalelaplusbasse

2.2Classificationdesalgorithmes

tionsdechoixaléatoiresparminvaleurs.

CHAPITRE2-Complexitéetalgorithmique19

cescritèresenparticulier.

Ilexistetroistypesdecomplexité:

del'algorithme; del'algorithme; rithme. lité.

20CHAPITRE2-Complexitéetalgorithmique

(g),sig=O(f) f(n)c2:g(n) (f(n))et(c)g(n)2(f(n)). n; parcourslinéairedesdonnées; del'autreboucleestauplusn;

CHAPITRE2-Complexitéetalgorithmique21

nN1100:N11000:N1 n2N210:N231;6:N2 n3N34;46:N310:N3 n5N42;5:N43;98:N4

2nN5N5+6;64N5+9;97

3nN6N6+4;19N6+6;29

Cettetableestissuede[53].

2.3Classificationdesproblèmes

2.3.1ClassesPetNP

22CHAPITRE2-Complexitéetalgorithmique

polynomial. lesuivant:

LESSEPTPONTSDEKÖNIGSBERG

unproblèmedelaclasseP.

CHAPITRE2-Complexitéetalgorithmique23

2.3.2LesproblèmesNP-complets

siP1/P2etP2/P3alorsP1/P3. P.

CrescenzietKann[41].

1.P2NP,

24CHAPITRE2-Complexitéetalgorithmique

détailsseréférerà[68]).

2.3.3PvsNP

machine. résolvablesentempspolynomial. question"P=NP?".

CHAPITRE2-Complexitéetalgorithmique25

2.4ContournerlaNP-complétude

2.4.1Branch-and-Bound

touteslessolutions.

26CHAPITRE2-Complexitéetalgorithmique

derechercheouarbrededécision?. séparationdesonespacedesolutions. contientpasl'optimum.

2.4.2Heuristique

2.4.3Approximation

R p(I)=max(Algo(I)

OptP(I);OptP(I)Algo(I))

CHAPITRE2-Complexitéetalgorithmique27

approchée.

àunfacteurprèspourleproblème.

décisionnelleestdansNP. etFPTAS. problème,pourtouteconstante>0. nentiellementde1 [81].

28CHAPITRE2-Complexitéetalgorithmique

App optimale. tellesque: oùestuneconstantestrictementpositive; strictementpositive.

Figure2.10-L-réductiondeP1versP2.

2.4.4Complexitéparamétrée

CHAPITRE2-Complexitéetalgorithmique29

l'instanceetkleparamètre. etcuneconstante. que: quelconqueetcuneconstante; k

0g(k).

illimitéd'entrées.

F;p(C)h(resp.8C2F;t(C)h).

30CHAPITRE2-Complexitéetalgorithmique

PARAMETERIZEDDECISIONCIRCUIT(PDCF)

uneprofondeurpetunetrametbornées.

FPTW[1]W[2]:::W[t]:::W[P]

PARTIEII

Comparaisondestructuresdemolécules

d'ARN

CHAPITRE3

Présentationgénérale

[64,100]; [31,96]. résultats.

3.1Lesséquencesarc-annotées

culesd'ARN. 33

S=S[1]S[2]:::S[jSj].

unarcdeP. séquencesarc-annotées: jl);

4.iln'yapasd'arcdutout(i.e.P=;).

UNLIMITED-pasderestrictions;

CROSSING-restriction1;

NESTED-restrictions1et2;

CHAIN-restrictions1,2et3;

PLAIN-restriction4.

P(UNLIMITED;UNLIMITED)

UNLIMITED.

n

2.P(n1;n2)P(n3;n4).

geurdecoupeetlalargeurdebande. d'ARN(leproblèmeAPS).

TàpartirdeS.

avecl'alphabet[fgtellesque81ijS0j:

Lesymboleestappelégap.

caractères"THESARD"et"RETARD"est:

THE-SAR-D

R-ET-ARD-

unalignement. S; suppression celuid'unesubstitutiond'arcestwam. pourcesdeuxniveauxdecomplexité.

Z-EDIT

CROSSINGNESTEDPLAIN

CROSSINGNP-complet[99]O(m2nlogn)[99]

PLAINO(nm)[59]

T caractèresmarqués. S; marquésetl'arc(i;j)estajoutéàP;

ôtédeP;

suppriméetl'arc(i;j)estôtédeP. sontprisesencompte.

L-EDIT

UNLIMITEDCROSSINGNESTEDPLAIN

UNLIMITEDMaxSNP-dur[75]

CROSSINGMaxSNP-dur[75]

NESTED?O(nm3)[75]

PLAINO(nm)[84]

wb+wr;wb+wr2wagpource sous-problème.

3.1.2.2LeproblèmeLAPCS

estunivoque:sisi=sjalorsti=tj; préservel'ordre:sisi8(si;ti)2C,U[i]=S[si]; (entermedeséquence)maximale.

MITED,CROSSING,NESTED,CHAINetPLAIN.

LAPCS

UNLIMITEDCROSSINGNESTEDCHAINPLAIN

UNLIMITEDNP-complet[48]

CROSSINGNP-complet[48]

NESTEDNP-complet[74]O(nm3)[65]

CHAINO(nm)[48]

PLAINO(nm)[63]

plexité. rithmesdecomplexitéparamétrée: séquencesarc-annotées; séquencesarc-annotées; LAPCS

UNLIMITEDCROSSINGNESTEDCHAINPLAIN

UNLIMITEDW[1]-completpourL

CROSSINGW[1]-completpourL;O(9xnm)O(9xnm)

NESTEDO(x24xnm)-

CHAIN-

PLAIN-

LAPCS

UNLIMITEDCROSSINGNESTEDCHAINPLAIN

CROSSINGMaxSNP-dur;2-approximable

NESTED2-approximable-

CHAIN-

PLAIN-

3.1.2.3LeproblèmeAPS

moléculesd'ARN[48,99]. arc-préservante:

ARC-PRESERVINGSUBSEQUENCE(APS)

jTjjSj. longueurjTj? arc-préservantecommesuit.

ARC-PRESERVINGSUBSEQUENCE(APS)

jTjjSj. APS

UNLIMITEDCROSSINGNESTEDCHAINPLAIN

UNLIMITEDNP-complet[48]

CROSSINGNP-complet[48]NP-complet[58]?

NESTEDO(nm)[57]

CHAINO(nm)[57]O(n+m)[57]

Table3.7-ComplexitéduproblèmeAPS.

problèmeAPS.

3.2Les2-intervalles

nommée2-intervalle. structuraux. lanotiond'intervalle. pas). destroisrelationssuivantes:

D1

D1@D2siI2

D1./D2siI1 modèledecomparaison. de2-intervallesdisjoints. sechevauchent,alorsI=I0. suivantsillustrésenFigure3.5:

UNLIMITED:aucunerestriction;

UNITARY:restriction1;

DISJOINT:restrictions1et2.

support:UNLIMITED,UNITARYetDISJOINT.

P(UNLIMITED;R)P(UNITARY;R)P(DISJOINT;R)

dusupport,8Rf<;@;./g.

2.Rf<;@;./g;

3.P(n1;R)P(n2;R).

n'ontpasétérespectées.

3.2.2.1Leproblème2-IP

2-INTERVALPATTERN(2-IP)

entierpositifk. soitR-comparable? n soudronstrois. 2-IP

SUPPORT

MODÈLEUNLIMITEDUNITARYDISJOINT

f<;@;./gNP-complet[94]O(npn)[78] f@;./gNP-complet[94]? f<;@gO(n2)[94] f<;./g? fSUPPORT

MODÈLEUNLIMITEDUNITARYDISJOINT

f<;@gpolynomial f3.2.2.2LeproblèmePMO-2

PMO-2sedéfinitcommesuit.

Rf<;@;./g.

QUESTION:Existe-iluneoccurrencedepdansD?

ProblèmePMO-2

SUPPORT

MODÈLEUNLIMITEDUNITARYDISJOINT

f<;@;./gNP-complet[94] f@;./gNP-complet[94] f<;@gO(mn3logn)[94] f<;./gO(n6m2)[56] fCHAPITRE4

LeproblèmeL-EDIT

4.1Introduction

L-EDIT

UNLIMITEDCROSSINGNESTEDPLAIN

UNLIMITEDMaxSNP-dur[75]

CROSSINGMaxSNP-dur[75]

NESTEDNP-complet[23]O(nm3)[75]

PLAINO(nm)[84]

connexeplanairesansisthmesi: 51

52CHAPITRE4-LeproblèmeL-EDIT

formé:

Chaquedemi-planestappelépage.

sommetsdeV0. TED)

MIS-3P

ouégaleàk? induitesparl'alignement.

L-EDIT(NESTED,NESTED)

entiers0. induitsoitinférieurouégalàs0?

CHAPITRE4-LeproblèmeL-EDIT53

NESTED)s'effectueendeuxtemps.

commesuit:

S=ScSv1ScSv2ScSv3:::ScSvnSc

T=TcTv1TcTv2TcTv3:::TcTvnTc

nombreqdeterminédebasesC,avecq>3nwr 4.2). a caspossiblessuivants:

54CHAPITRE4-LeproblèmeL-EDIT

TED)résultantdelaUA-construction.

tempspolynomial. lementleparamètres0=3n(wb+4wd w a>wb>wd>0(4.1) w r>wa+wd(4.2) w b+wd

3>wa(4.3)

CHAPITRE4-LeproblèmeL-EDIT55

wm>2wr(4.4) onnommecetteopérationarc-match);

Danscecas,Score(A2)Score(A1)=2wdwm

sous-cas: tionàungap.

Danscecas,Score(A2)Score(A1)=2wa(2wb+wm)

tutionàungap.

Danscecas,Score(A2)Score(A1)=2wr(2wa+wm)

56CHAPITRE4-LeproblèmeL-EDIT

i emesegmentTcdeT,pourtout1in+1. alignementcanoniquedeSetT. Cas1. telquek6=m,commel'illustrelaFigure4.2.

Figure4.2-Alignementcroisé.

unebaselibrepeutêtremajoréparwr

2

2pourchacunedesbasesmarquées),

2également.

2,onaScore(A2)<6nwr.

CHAPITRE4-LeproblèmeL-EDIT57

donnéqueq>3nwr A S dix-huitcasillustrésenFigure4.3. t deSsoitdorénavantsurTetvice-versa). symétriquesontunscoreidentique. detypestg,tua,tgSymettuaSym. t

58CHAPITRE4-LeproblèmeL-EDIT

quotesdbs_dbs22.pdfusesText_28

[PDF] 2 L 'ADN, support universel de l 'information génétique

[PDF] Utilisation d 'Acrobat X Professional - Adobe

[PDF] Guide d utilisation de la lecture audio d Adobe Reader

[PDF] La crise d 'adolescence entre crise familiale et crise de la société

[PDF] Salud para los adolescentes del mundo

[PDF] Adolescencia Una etapa fundamental - Unicef

[PDF] Las metamorfosis de la pubertad y el despertar de la primavera

[PDF] DES CONSEILS POUR MON ENFANT QUI EST ISOLÉ ET REJETÉ

[PDF] Livre:Thiers Adolphe - Histoire de la Révolution française t1 (1839

[PDF] La romanisation de la Gaule On appelle romanisation l adoption du

[PDF] Adorer Dieu en esprit et en vérité - Mennonite World Conference

[PDF] Qu 'est-ce qu 'un chevalier - BnF - Expositions virtuelles

[PDF] Autosomal Dominant Polycystic Kidney Disease: Core Curriculum

[PDF] Adressage IP

[PDF] Packet Tracer : configuration de l 'adressage IPv6