Cette thèse vise à étudier deux problématiques différentes: 1) la reconnaissance des activités de la vie quotidienne des personnes dans un habitat intelligent, et 2) la construction du profil comportemental de la personne. Nos contributions sont présentées dans deux chapitres illustrant les solutions proposées. La première contribution de cette thèse est liée à l'introduction d'une nouvelle approche non supervisée de reconnaissance d'activités nommée ADR-SPLDA (Activity Discovery and Recognition using Sequential Patterns and Latent Dirichlet Allocation). Contrairement aux approches existantes, ADR-SPLDA permet la découverte et la reconnaissance des activités de façon non supervisée sans faire nécessairement recours à l'annotation des données. En outre, ADR-SPLDA est basée sur l'analyse de patrons fréquents, ce qui permet de réduire significativement la quantité du bruit dans les données. La fiabilité de ADR-SPLDA est illustrée à travers une série de tests et de comparaisons avec les approches existantes sur une variété de données réelles. Le deuxième travail vise la construction du profil comportemental de la personne en se basant sur ses activités. Nous avons développé une approche qui permet de découvrir les différents comportements dans les séquences, et d'extraire les relations causales entre les différents comportements. Notre contribution inclut l'introduction de l'analyse causale dans la construction du profil, ce qui nous a permis aussi de découvrir les relations causales entre les différentes activités. Une série de tests a été également effectuée pour illustrer la fiabilité de notre approche sur une variété de données. Le travail de recherche entrepris dans cette thèse constitue l'une des nombreuses étapes importantes dans l'accomplissement d'un système d'assistance efficace dans l'objectif d'assurer le bien-être des personnes.

Le nombre d’enfants nés par Assistance Médicale à la Procréation (AMP) dans le monde est estimé à plus de 5 millions, représentant jusqu’à 4% des naissances. Environ 10% des couples en âge de procréer sont actuellement infertiles, et leur apporter des techniques pour devenir parents est devenu un problème de santé publique. Cependant, l’innocuité de ces techniques n’a pas été totalement démontrée. Notamment, le risque de pathologies d’origine placentaire pourrait être augmenté. De plus, des issues périnatales défavorables, un risque majoré de malformations majeures et de pathologies liées à l’empreinte ont été rapportés chez ces enfants. Ceci soulève la question d’une éventuelle vulnérabilité épigénétique induite par l’AMP. L’objectif de ce travail de thèse était d’étudier la régulation épigénétique des gènes soumis à empreinte (GSE) et des éléments transposables (TE) dans le placenta et le sang de cordon d’enfants conçus par AMP comparés à des enfants conçus naturellement. En guise d’introduction, nous avons rédigé une revue détaillée des modifications phénotypiques et épigénétiques induites par l’AMP dans les embryons, le placenta et le sang de cordon chez l’Homme et sur les modèles animaux.Au cours de cette thèse, une cohorte de presque 250 patientes a été incluse prospectivement, répartie en 4 groupes de patientes selon la technique d’AMP et 4 groupes de témoins selon la durée d’infertilité.A partir de cette cohorte, la première question posée a été l’effet de la Fécondation in vitro (FIV) sur la méthylation de l’ADN et/ou la transcription des GSE et TE dans le sang de cordon et le placenta à la naissance. Pour cela, nous avons sélectionné 51 patientes enceintes après FIV avec ou sans ICSI avec transfert d’embryon frais à J2 et les avons comparées à 48 témoins enceintes dans l’année après l’arrêt de la contraception. Nous avons étudié la méthylation de l’ADN et l’expression de 3 GSE et 4 TE. Les niveaux de méthylation de l’ADN placentaire pour H19/IGF2, KCNQ1OT1, LINE-1 et ERVFRD-1 et le niveau d’expression placentaire d’ERVFRD-1 étaient plus bas dans le groupe FIV/ICSI que dans le groupe contrôle. Ces modifications épigénétiques pourraient faire partie des mécanismes de compensation développés pendant la grossesse après AMP, comme discuté dans notre revue.Ensuite, nous avons voulu déterminer si ces changements de méthylation de l’ADN des GSE pouvaient être associés à des modifications des histones. A partir de la cohorte précédente, nous avons sélectionné 16 patientes du groupe FIV/ICSI avec des niveaux de méthylation dans le placenta inférieurs au 5ème percentile pour au moins un des GSE étudiés. Elles ont été appariées à 16 témoins sur la parité, le sexe du nouveau-né et l’âge gestationnel à l’accouchement. Des marques permissives (H3K4me2 et me3 et H3K9ac) et répressives (H3K9me2 et me3) ont été étudiées. Les résultats ont révélé une quantité significativement augmentée de H3K4me2 dans le groupe FIV/ICSI pour H19/IGF2 et KCNQ1OT1. La quantité des deux marques répressives pour H19/IGF2 et SNURF était significativement abaissée dans le groupe FIV/ICSI.Ces données montrent que l’hypométhylation de l’ADN au niveau des GSE pourrait être associée à une augmentation des marques permissives et une diminution des marques répressives des histones, ce qui permettrait de favoriser un état « actif » de la chromatine au niveau de l’allèle normalement réprimé.Nos résultats, ainsi que les données de la littérature, renforcent l’hypothèse de potentiels mécanismes mis en place dans le placenta après AMP, utiles pour compenser des anomalies précoces de la placentation, qui seraient écrits à travers des modifications épigénétiques comme la méthylation de l’ADN mais aussi les modifications des histones.Bien que certaines questions restent en suspens, cette thèse a permis de bâtir les fondations de travaux futurs, notamment pour étudier l’impact de la congélation/décongélation des embryons et le rôle joué par l’infertilité en elle-même. / It is estimated that more than five million children have been born by Assisted Reproductive Technologies (ART) worldwide, representing up to 4% of all births. As around 10% of reproductive-aged couples are currently infertile, providing them with treatment options is a public health issue. However, the safety of these techniques has not been fully demonstrated. Notably, the rate of placenta-related adverse pregnancy outcomes could be increased after ART. Moreover, adverse perinatal outcomes, a higher risk of major malformations and imprinting disorders have also been reported in children born following ART. These issues combined raise the question of a potential ART-induced epigenetic vulnerability.The aim of this thesis was to investigate the epigenetic regulation of imprinted genes (IGs) and transposable elements (TEs) in the placenta and cord blood of children conceived by ART and to compare them to children conceived naturally.By way of introduction, we wrote a comprehensive review about phenotypic and epigenetic modifications induced by ART in embryos, placenta and cord blood either in human or animal models.Then, an extensive cohort of almost 250 patients was prospectively included, resulting in 4 groups of ART techniques and 4 groups of controls stratified on the time to pregnancy.From this cohort, the first question we investigated was the effect of in vitro fertilization (IVF) on DNA methylation and/or transcription of TEs and IGs in cord blood and placenta collected at birth. For this purpose, we selected 51 pregnant women after IVF with fresh embryo transfer at day -2 and compared them with 48 controls pregnant within 1 year of stopping contraception. We studied the DNA methylation and expression of 3 imprinted DMRs and 4 TEs. DNA methylation levels for H19/IGF2 and KCNQ1OT1 DMRs, LINE-1 and ERVFRD-1 in the placenta were lower in the IVF/ICSI group than in the control group. The expression level of ERVFRD-1 in the placenta was also lower in the IVF/ICSI group than in the control group. These modifications in epigenetic regulation may influence some compensation mechanisms developed throughout pregnancy after ART, as discussed in our review.We then intended to determine if these DNA methylation changes in IGs were associated with histone modifications. From the previously mentioned cohort, we selected the 16 patients from the IVF/ICSI group who presented with below the 5th percentile of percentage placenta DNA methylation for at least one of the previously studied DMRs. These patients were compared with 16 controls matched for parity, new-born sex, and gestational age at delivery. Permissive (H3K4me2 and me3 and H3K9ac) and repressive (H3K9me2 and me3) histone marks were studied. The results revealed a significantly higher quantity of H3K4me2 in the IVF/ICSI group than in the natural conception group for H19/IGF2 and KCNQ1OT1 DMRs. The quantity of both repressive marks at H19/IGF2 and SNURF DMRs was significantly lower in the IVF/ICSI group than in the natural conception group.These data demonstrate that DNA hypomethylation at imprinted DMRs may be associated with an increase in permissive histone marks and a decrease in repressive histone marks. This is consistent with a more “active” chromatin conformation on the normally repressed allele.Our findings, together with the literature data, reinforce the hypothesis that some mechanisms are established in the placenta after ART, probably to mediate placental plasticity and compensate primary disorders in trophoblastic invasion, and written through epigenetic changes such as DNA methylation but also histone modifications.Although some questions remain unanswered, this thesis paves the way for further original studies, notably to assess the impact of frozen-thawed embryo transfer and to decipher the role of infertility per se.

Les volumes des données générées par les technologies de séquençage haut débit augmentent exponentiellement ce dernier temps. Le stockage, le traitement et le transfertdeviennent des défis de plus en plus sérieux. Pour les affronter, les scientifiques doivent élaborer des approches et des algorithmes de plus en plus efficaces.Dans cette thèse, nous présentons des structures de données efficaces etdes algorithmes pour des problèmes de recherche approchée de chaînes de caractères, d'assemblagedu génome, de compression de séquences d’ADN et de classificationmétagénomique de lectures d’ADN.Le problème de recherche approchée a été bien étudié, avec un grandnombre de travaux publiés. Dans ledomaine de bioinformatique, le problème d’alignement de séquences peut être considéré comme unproblème de recherche approchée de chaînes de caractères. Dans notre travail, nousétudions une stratégie de recherche basée sur une structure d'indexation ditebidirectionnelle. D’abord, nous définissons un formalisme des schémas de recherche pour travailleravec les stratégies de recherche de ce type, ensuite nous fixons une mesure probabiliste del’efficacité de schémas de recherche et démontrons quelques propriétés combinatoires de schémasde recherche efficaces. Finalement, nous présentons des calculs expérimentaux quivalident la supériorité de nos stratégies. L’assemblage du génome est un des problèmes clefs en bioinformatique.Dans cette thèse, nous présentons une structure de données — filtre de Bloom en Cascade— qui améliore le filtre de Bloom standard et peut être utilisé pour larésolution de certains problèmes, y compris pour l’assemblage du génome. Nousdémontrons ensuite des résultats analytiques et expérimentaux sur les propriétés du filtre deBloom en Cascade. Nous présentons également comment le filtre de Bloom en Cascade peut être appliqué au problèmede compression de séquences d’ADN.Un autre problème que nous étudions dans cette thèse est la classificationmétagénomique de lectures d’ADN. Nous présentons une approche basée sur la transforméede Burrows-Wheeler pour la recherche efficace et rapide de k-mers (mots de longueur k).Cette étude est centrée sur les structures des données qui améliorent lavitesse et la consommation de mémoire par rapport à l'index classique de Burrows-Wheeler, dans le cadre de notre application / Amounts of data generated by Next Generation Sequencing technologies increase exponentially in recent years. Storing, processing and transferring this data become more and more challenging tasks. To be able to cope with them, data scientists should develop more and more efficient approaches and techniques.In this thesis we present efficient data structures and algorithmic methods for the problems of approximate string matching, genome assembly, read compression and taxonomy based metagenomic classification.Approximate string matching is an extensively studied problem with countless number of published papers, both theoretical and practical. In bioinformatics, read mapping problem can be regarded as approximate string matching. Here we study string matching strategies based on bidirectional indices. We define a framework, called search schemes, to work with search strategies of this type, then provide a probabilistic measure for the efficiency of search schemes, prove several combinatorial properties of efficient search schemes and provide experimental computations supporting the superiority of our strategies.Genome assembly is one of the basic problems of bioinformatics. Here we present Cascading Bloom filter data structure, that improves standard Bloom filter and can be applied to several problems like genome assembly. We provide theoretical and experimental results proving properties of Cascading Bloom filter. We also show how Cascading Bloom filter can be used for solving another important problem of read compression.Another problem studied in this thesis is metagenomic classification. We present a BWT-based approach that improves the BWT-index for quick and memory-efficient k-mer search. We mainly focus on data structures that improve speed and memory usage of classical BWT-index for our application

Les ISCR constituent une famille de séquences d’insertions bactériennes décrits récemment dans des contextes cliniques et d’antibiorésistance. Les transposases codées par ces IS appartiennent à la famille des HUH transposases qui transposent selon un mécanisme en cercle roulant. Néanmoins, aucune donnée expérimentale n’existe à ce jour. La famille ISCR compte 19 membres mais ont été peu caractérisés. C’est pourquoi, nous avons fait une mise à jour des informations sur ces éléments en analysant in silico les principales caractéristiques par une étude in silico. Nous nous sommes ensuite intéressés à l’implication de l’élément ISCR1 dans l’expression de la région variable en aval. Cet élément contient deux promoteurs orientés vers l’extérieur (POUT) dans sa région en 3’. Après une analyse de la diversité des gènes, nous avons remarqué que la plupart des gènes en aval étaient orientés dans le même sens que ces POUT et qu’ils pouvaient être exprimés à partir des deux promoteurs. Nous avons montré que pour deux gènes de résistance dfrA19 et blaCTX-M-9, ces promoteurs augmentent le niveau d’expression. De plus, la région contenant les deux promoteurs est nécessaire pour que l’expression de blaCTX-M-9 confère un phénotype de résistance. En parallèle, nous avons déterminé la régulation du promoteur du gène de la transposase de ISCR1. Nous avons identifié des motifs de régulation pour les régulateurs LexA et OmpR et déterminé expérimentalement que le promoteur du gène de la transposase de ISCR1 était régulé de façon négative par la protéine LexA, régulateur majeur de la réponse SOS et de façon positive par la protéine OmpR en conditions hypo-osmotiques. Nous proposons donc un modèle selon lequel ISCR1 est un élément dont la mobilité serait conditionnée par des facteurs environnementaux et en même temps, assurerait l’expression constitutive de gènes en aval, notamment impliqués dans l’antibiorésistance. / ISCR are a bacterial insertion sequences, recently described in clinical settings, frequently related to antibiotic resistance. These ISCR-encoded transposases belong to the well-known HUH transposases family, which transpose by rolling-circle replication. However, the transposition mechanism of ISCR transposases has not been shown experimentally. ISCR family includes 19 members and has not been well characterized yet. Therefore, we updated in silico already known characteristics for each ISCR element. Then, we investigated the involvement of ISCR1 in the expression of the downstream genes. Indeed, ISCR1 carries two outward-oriented promoters called POUT. By analyzing the diversity of the downstream region, we found that most of genes were in the same orientation as POUT promoters, suggesting these downstream genes are expressed from POUT. It thus showed that these two promoters are able to express two antibiotic resistance genes (dfrA19 and blaCTX-M-9 ). Moreover, the region containing POUT is essential to provide an ESBL-resistance phenotype for blaCTX-M-9 gene. Moreover, we also wanted to analyze the regulatory network involved in the expression of the ISCR1 transposase, RCR1. We experimentally determined that two regulatory proteins LexA and OmpR, involved in response to different stress (DNA damages and osmotic shock), control the activity of rcr1 promoter. LexA protein represses Prcr1 whereas OmpR activates Prcr1 in hypo-osmotic conditions. Here, we propose a model in which ISCR1 transposition would be the control of environmental stresses and at the same time, insured the expression of downstream antibiotic resistance genes.

Les méthodes de recherche de similarités les plus fréquemment utilisées dans le cadre de la génomique sont heuristiques.<br />Elles se basent sur un principe de filtrage du texte qui permet de localiser les régions potentiellement similaires.<br />Dans cette thèse, nous proposons de nouvelles définitions de filtres pour la recherche de similarités sur les séquences génomiques et des algorithmes associés pour mesurer leurs caractéristiques.<br /> Plus précisément, nous avons étudié le modèle des graines espacées, et proposé un algorithme d'évaluation de l'efficacité des graines sur des similarités d'une classe particulière (similarités dites homogènes). Nous avons également développé un algorithme général pour la mesure de l'efficacité des graines, ainsi qu'un nouveau modèle de graine appelé graine sous-ensemble, extension du modèle des graines espacées. Enfin nous donnons, dans le cadre du filtrage sans perte, une extension à l'aide de graines multiples, que nous analysons et appliquons au problème de la conception d'oligonucléotides.<br /> Nous avons réalisé et donnons accès à des outils pour la conception des filtres, ainsi que pour la recherche de similarités.

Le gène est défini comme une unité fonctionnelle de l'hérédité. En effet, les gènes, transcrits en ARN, codent pour des protéines qui assurent l'essentiel des fonctions cellulaires. Cependant, les gènes ne représentent que 2% du génome humain. Ainsi, notre génome est presque exclusivement composé d'ADN non codant (ADNnc) qui, en raison d'une absence apparente de fonction (c'est-à-dire de transcription et de traduction), est également connu sous le terme peu élogieux d' « ADN poubelle ». De manière surprenante, la quantité d'ADNnc présente dans les cellules est proportionnelle au degré de complexité des organismes, suggérant ainsi que cet ADNnc pourrait avoir une fonction. En particulier, les centromères et des péricentromères, qui contiennent des séquences d'ADNnc de type satellite, permettent la ségrégation correcte de chromatides sœurs lors de la mitose. De plus des études récentes réalisées chez la levure S.pombe montrent que les régions péricentromériques peuvent être transcrites. Les ARNnc ainsi produits participent à l'établissement et au maintien de l'hétérochromatine péricentromérique. Bien que les mécanismes impliqués dans ces processus soient en grande partie identifiés, très peu de choses sont connues quant à la capacité transcriptionnelle de ces séquences satellites chez d'autres espèces.<br /><br />Ainsi, l'objectif de ma thèse a été d'évaluer le potentiel transcriptionnel des séquences satellites du génome humain.<br /><br />A mon arrivée dans le laboratoire, l'équipe du Pr Claire Vourc'h était particulièrement engagée dans ce projet puisqu'elle venait de mettre en évidence la transcription des séquences satellites 3 du locus 9q12 au cours de la réponse au stress. Mon travail de thèse m'a conduit à approfondir cette étude en identifiant de nouvelles séquences satellites dont la transcription est induite par le stress thermique. Par ailleurs, j'ai développé la première approche trancriptomique dédiée à l'expression des séquences satellites du génome humain : la RepChip. Le modèle de la réponse au stress m'a permis de valider cet outil. Ainsi, j'ai pu identifier non seulement de nouveaux contextes cellulaires permettant l'expression de ces séquences mais également deux mécanismes indépendants impliqués dans leur transcription. En particulier, un lien entre la capacité transcriptionnelle de ces séquences et des modifications de l'épigénome a pu être établi. Finalement, j'ai identifié un modèle d'inhibition de la transcription des séquences satellites au cours du choc thermique, le syndrome ICF (Immunodeficiency, Centromeric instability and Facial anomalies).

L'objectif de mon doctorat est de développer une méthode d'analyse des séquences protéiques permettant de cribler, le plus efficacement possible, les alignements non significatifs produits par le logiciel PSI-BLAST afin d'identifier des relations d'homologies lointaines. La stratégie développée repose sur deux étapes de criblage, une première s'appuyant sur les prédictions de structures secondaires, une seconde tirant profit du développement récent de méthodes de comparaison profil/profil performantes. La méthode développée a été initialement calibrée sur une base de données de séquences particulière. Cette base rassemble des séquences de domaines dont les structures sont connues permettant ainsi de contrôler l'existence effective d'homologues lointains. Cette phase a permis d'établir les seuils de détection optimaux permettant une utilisation semi-automatique du programme. Dans une seconde phase, la méthode a été testée sur un ensemble de 100 protéines impliquées dans la signalisation et la réparation des dommages de l'ADN. Au travers de différents exemples, nous montrons les potentialités du programme développé pour des recherches d'homologies lointaines à grande échelle. En particulier, mon étude suggère une nouvelle hypothèse pour comprendre l'origine d'une maladie rare, le syndrome de Nijmejen, provoqué par une mutation dans la protéine Nbs1.

J'ai travaillé sur les problèmes de modélisation du vivant avec l'hypothèse fondamentale qu'il s'agit de machines symboliques et la volonté d'aider le chercheur en biologie à traiter avec le bon niveau d'abstraction ces machines. Le cœur de mes travaux considère les ensembles de séquences que forment les macromolécules du vivant comme des langages formels et cherche à approfondir les concepts nécessaires pour mener à bien leur analyse linguistique. Il faut tout d'abord étudier le contenu lexical des séquences génomiques, son vocabulaire. Au niveau élémentaire, les facteurs répétés fournissent les unités de sens de la séquence. Cependant, la notion naturelle de répétition dans l'ADN est beaucoup plus complexe et nécessite à la fois d'être formalisée et d'être accompagnée d'une algorithmique de recherche spécialisée. J'ai particulièrement développé cet aspect dans l'étude d'éléments génétiques mobiles à l'intérieur d'un génome ou entre deux génomes. J'ai également travaillé sur le niveau syntaxique, ce qui a mené à l'élaboration d'un langage, Logol, qui permet au biologiste de construire un modèle grammatical hypothétique puis de le tester sur des séquences génomiques. Le langage défini autorise en particulier une notion de variable de chaîne avec une face abstraite qui représente la chaîne d'origine et une face concrète pour les différentes instances copies de cette chaîne d'origine. Ce cadre a été validé sur plusieurs problèmes biologiques de recherche de protéines ou d'éléments génétiques, dont la découverte de récepteurs olfactifs chez le chien et la découverte de défensines humaines. Lorsqu'aucun modèle n'est disponible, il faut tenter de l'inférer à partir d'exemples de séquences. J'ai lancé une série de recherches tant théoriques que pratiques sur ce thème. Au niveau théorique, le problème difficile de l'inférence de grammaires algébriques a été abordé à partir d'ordres partiels sur les non-terminaux ou les arbres de dérivation. La classe mieux maîtrisable des langages réguliers a fait l'objet des travaux les plus approfondis, sur une représentation par automates d'états finis. L'inférence devient alors un problème d'optimisation par gestion d'un ensemble de contraintes dynamiques sur les équivalences d'états. Du point de vue pratique, nous avons tout particulièrement étudié ces problèmes d'inférence sur des séquences de protéines, par exemple en étudiant la prédiction de certaines liaisons (ponts disulfures) entre des sites distants sur la séquence. Enfin, je propose à la fin de mon document d'habilitation un projet pour aborder de façon plus transdisciplinaire la modélisation du vivant en tant que machine symbolique. Les questions que pose la biologie, science expérimentale par excellence, s'expriment majoritairement en termes de raisonnement hypothétique. Je propose de mener des recherches en vue de la mise au point d'un assistant d'expérimentation biochimique sur puce sur cultures cellulaires. Le but global est le développement d'un environnement permettant de relier en boucle expérimentation, observations et acquisition de connaissances, en utilisant un système complet de raisonnement automatique (apprentissage abductif et inductif et planification).

L'alignement multiple est une opération permettant de mettre en évidence la similarité entre plusieurs séquences. Il est notamment utilisé pour la reconstruction de phylogénies, la recherche de motifs et la prédiction de structures. Cette thèse s'intéresse au développement de nouveaux algorithmes pour ce problème particulièrement difficile, et introduit deux algorithmes progressifs ayant pour point commun de réaliser un alignement multiple par alignements successifs de groupes de séquences.<br />Le premier algorithme, Plasma utilise une méthode de descente, dont chaque itération consiste à réaliser des insertions de colonnes de brèches dans deux alignements multiples à aligner. Le second algorithme, Plasma II , est basé sur le principe de la programmation dynamique. Nous généralisons ici l'algorithme utilisé pour l'alignement de deux séquences, et étendons le cadre de la programmation dynamique `a l'alignement de deux alignements multiples. Cet algorithme ainsi que plusieurs variantes sont intensivement évalués sur les jeux d'essais de Balibase, montrant des résultats encourageants, voire compétitifs, par rapport à certains algorithmes de référence comme Clustal W, tant sur la qualité de l'alignement que sur le temps de calcul.

Je présente dans ce manuscrit mes travaux de recherche effectués depuis la thèse. Mes thèmes de recherche sont principalement motivés par des applications en génomique ou post-génomique. Mon domaine de recherche est assez vaste, mais le dénominateur commun de mes travaux est la présence de variables latentes (non observées) dans les modèles étudiés. Mes préoccupations sont majoritairement théoriques : éudes asymptotiques, convergence des estimateurs, vitesses, identifiabilité... Les modèles considérés peuvent être aussi bien paramétriques que semi ou non paramétriques, et les outils statistiques utilisés sont donc relativement variés.<br /><br />Ma présentation s'organise en trois grandes thématiques : les travaux portant sur des séquences, notamment sur la modélisation de leur distribution et des processus d'évolution sous-jacents ; les travaux de statistique semi ou non paramétrique portant sur des signaux observés avec du bruit ; et enfin les travaux (en partie en cours) portant sur les graphes aléatoires.