Nous étudions dans cette thèse le problème de l’exploration parallèle d’un graphe à l’aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visiter les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe.Nous étudions d’abord l’exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les noeuds n’ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s’exécutent dans un minimum de temps possible pour polynomiale nombre d’agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l’impact de différentes méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire,mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes.Nous considérons également l’exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d’un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l’accélération défini comme la proportion entre le pire des cas de l’exploration d’un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d’agents. Nous présentons également des résultats optimaux sur l’accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes.Finalement nous considérons l’exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l’exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l’exploration des graphes. / In this thesis we study the problem of parallel graph exploration using multiple synchronized mobile agents. Each mobile agent is an entity that can, independently of other agents, visit vertices of the graph and traverse its edges. The goal of the agents is to visit all vertices of the graph. We first study graph exploration in the model where agents are equipped with internal memory but no memory is available at the nodes. Agents in this model are also allowed to communicate between each other by exchanging messages. We present algorithms working in a minimal possible time for a team of polynomial size (in the number of vertices of the graph). We also study the impact of the available range of communication by analysing algorithms for agents which can communicate at arbitrary distance, or only with other agents located at the same node. We present efficient algorithms and lower bounds that almost match our positive results in both communication models. We also consider graph exploration when movements of agents are determined according to the so-called rotor-router mechanism. From the perspective of a fixed node, the rotor-router sends out agents which visit the node along its outgoing edges, ina round-robin fashion. We study the speedup which is the ratio between the worst-case exploration of a single agent and of multiple agents. We first show that the speed up for general graphs for the multi-agent rotor-router is always between logarithmic and linear in the number of agents. We also present a tight analysis of the speedup for the multi-agent rotor-router for cycles, expanders, random graphs, cliques, constant dimensional tori and an almost-tight analysis for hypercubes. Finally we consider collision-free exploration, where each agent has to explore the graph independently with the additional constraint that no two agents can occupy the same node at the same time. In the case when agents are given the map of the graph, we show an optimal algorithm for trees and an asymptotically optimal algorithm for general graphs. We also present algorithms for collision-free exploration of trees and general graphs in the case when agents have no initial knowledge about the graph. We close the thesis with concluding remarks and a discussion of related open problems in the area of graph exploration.

Les réseaux neuronaux profonds sont des outils prometteurs pour l'évaluation de la biodiversité aviaire, en particulier pour la détection des chants et la classification acoustique des espèces. Toutefois, on connaît mal l’étendue de leur capacité de généralisation face à la variation intraspécifique présente dans les chants d’oiseaux, ce qui pourrait mener à des biais. Notre étude porte sur l'évaluation des performances de BirdNET, un réseau neuronal profond, pour le traitement d’un corpus d'enregistrements audio caractérisés par une variation intraspécifique significative, en utilisant l’exemple du chant du bruant des prés (Passerculus sandwichensis). Dans la population de l'île de Kent, au Nouveau-Brunswick, les individus sont suivis et enregistrés grâce à leurs bagues de couleur et la présence de microdialectes est solidement documentée. Nous avons recueilli et annoté 69 606 chants provenant de 52 individus et analysé ces données à l'aide d’une version récente de BirdNET. Nos résultats révèlent que BirdNET démontre une précision globale suffisante, prédisant correctement 81,9 % des chants, ce qui dépasse les résultats rapportés par ses développeurs. Toutefois, nous avons observé une variation considérable dans les scores de confiance et les taux de prédiction exactes entre les individus, ce qui suggère des biais potentiels. Cependant, nos recherches n'ont pas mis en évidence de variation entre les résultats des différents microdialectes, ce qui souligne la relative robustesse de l'algorithme. Nous avançons que la variation observée entre les individus est due au fait que certains d’entre eux chantent systématiquement plus près des microphones, résultant en des chants plus clairs donc plus faciles à identifier. Pour mieux comprendre le processus de prise de décision de BirdNET, nous avons tenté de produire des cartes d'activation de classe, qui constituent un outil précieux pour identifier les éléments d’un chant qui déterminent une prédiction. Cependant, il ne nous a pas été possible d’obtenir des cartes d’activation de classe d’après la version actuellement disponible du code de BirdNET sans avoir recours à des connaissances avancées en informatique. L'accès à des outils explicatifs adaptés aux innovations récentes dans les architectures de réseaux neuronaux 4 profonds serait crucial pour mieux interpréter les résultats et renforcer la confiance des utilisateurs. Nos résultats soulignent la nécessité de poursuivre les recherches sur la capacité de généralisation des réseaux neuronaux profonds pour la bioacoustique en utilisant des ensembles de données monospécifiques portant sur de plus longues périodes ou des aires de répartition géographique plus vastes. En outre, l'extension de cette étude à des espèces ayant des répertoires plus importants ou des différences plus subtiles entre le chant des individus pourrait nous informer davantage sur les limites et le potentiel des algorithmes d'apprentissage profond pour la détection et la classification acoustiques des espèces. En conclusion, notre étude démontre les performances prometteuses de BirdNET pour le traitement d'un large corpus de chants de bruants des prés, et confirme son potentiel en tant qu'outil précieux pour l'évaluation de la biodiversité aviaire. Les biais dus aux techniques d’enregistrement et la variation dans les taux de succès observés entre les individus méritent d'être étudiés plus en détail. / Machine learning, particularly deep neural networks, has gained prominence as a valuable tool in ecological studies and wildlife conservation planning. In the field of avian biodiversity assessment, deep neural networks have shown remarkable promise, particularly in acoustic species detection and classification. Despite their success, a critical knowledge gap exists concerning the generalization ability of these algorithms across intraspecific variation in bird song. This raises concerns about potential biases and misinterpretation of results. This study focuses on evaluating the performance of BirdNET, a deep neural network, in processing audio recordings characterized by significant intraspecific variation in the Savannah Sparrow (Passerculus sandwichensis) song. Savannah Sparrows are an ideal candidate for this investigation, given their well-studied population on Kent Island, New Brunswick, Canada. Each male sings a unique, unchanging song throughout its life, and the population exhibits well-documented geographical microdialects. We collected a large corpus of Savannah Sparrow songs using autonomous and focal recorders on Kent Island, yielding a total of 69,606 manually annotated songs from 52 different sparrows. We analyzed the audio data using BirdNET-Analyzer. The resulting confidence scores were used to assess the algorithm's performance across microdialects and individual birds. Our results revealed that BirdNET exhibited considerable overall accuracy, correctly predicting 81.9% of the songs, which surpassed the results reported by the developers of BirdNET. We observed variations in BirdNET's confidence scores among individual birds, suggesting potential biases in its classifications. However, our investigation indicated no evidence of distinct biases towards specific microdialects, highlighting the algorithm's relative robustness across these groups. We suspect that the variation observed amongst individuals is caused by the fact that some were singing consistently closer to microphones, yielding clearer songs. To gain insights into BirdNET's decision-making process, we sought to employ class activation maps, a valuable tool for identifying essential song elements contributing to species predictions. However, we were unable to produce class activation maps from the current version of BirdNET 6 without advanced computer science skills. Access to informative tools adapted to recent innovations in deep neural network architectures for bioacoustic applications is crucial for understanding and interpreting results better. Such tools would enhance user confidence and favour accountability for conservation decisions based on these predictions. Our findings underscore the need for further research investigating the generalization capacity of deep neural networks in bioacoustics on single-species datasets with more extensive intraspecific variation and broader geographical ranges. Additionally, expanding this investigation to species with larger song repertoires or more subtle inter-individual song differences could provide valuable insights into the limits and potential of deep learning algorithms for acoustic species detection and classification. In conclusion, our study demonstrates BirdNET's promising performance in processing a large corpus of Savannah Sparrow songs, highlighting its potential as a valuable tool for avian biodiversity assessment. Biases and variations in confidence scores observed across individual birds warrant further investigation.

La leucémie aiguë lymphoblastique (LAL) est une maladie complexe à l’étiologie multifactorielle. Elle représente la forme la plus commune de cancer pédiatrique et malgré une augmentation significative du taux de survie des patients, près de 15% d’entre eux ne répondent pas aux traitements classiques et plus de 2/3 subissent les effets du traitement à long terme. Réduire ces chiffres passe par une meilleure compréhension des causes sous-jacentes de la LAL. À travers l’analyse des données de séquençage de nouvelle génération (SNG) de la cohorte QcALL du CHU Sainte-Justine, je me suis intéressé aux déterminants génomiques contribuant aux différents aspects de la LAL (prédispositions, développement/progression et rechutes). Dans un premier temps, j’ai développé un outil d’analyse (SNooPer) basé sur un algorithme d’apprentissage intégrant les données SNG normales et tumorales des patients, permettant d’identifier les mutations somatiques au sein de données à faible couverture (low-pass). Cet outil, couplé aux analyses prédictives in silico et aux validations fonctionnelles adéquates, nous a permis de caractériser les événements rares ou récurrents impliqués dans le processus leucémogène. En analysant les données de LALs pré-B, j’ai pu mettre en évidence une série de mutations drivers rares au niveau de gènes (ACD, DOT1L, HCFC1) qui n’avaient jamais été associés à la LAL. L’étude fonctionnelle de la mutation identifiée au niveau d’ACD, membre du complexe shelterin, a démontré qu’elle conduit à une réduction de l’apoptose et une augmentation de la taille des télomères. Outre l’intérêt de la découverte de ces nouveaux drivers, je souhaitais démontrer l’importance des mutations somatiques rares afin d'établir la spécificité interindividuelle, généralement sous-estimée, et d’identifier l’ensemble des fonctions cellulaires impliquées. Au cours de ces travaux, j'ai également mis en évidence de nouveaux évènements récurrents de la LAL à cellules T (LAL-T), en particulier au niveau de patients présentant un phénotype immature encore mal caractérisé. J'ai démontré l’influence d'une mutation dans le gène codant pour U2AF1, membre de la machinerie d’épissage (spliceosome), sur l’épissage de gènes d’intérêt et ainsi confirmer l’importance du dysfonctionnement de l’épissage dans le développement de la leucémie. J'ai également identifié deux suppresseurs de tumeurs portés par le chromosome X, MED12 et USP9X, qui n’avaient jamais été associés à la LAL-T auparavant et qui représentent un intérêt particulier étant donné le débalancement de l'incidence en fonction du sexe (ratio garçon:fille =1.22). Enfin, grâce à l’étude longitudinale de patients LAL-B ayant subi une ou plusieurs rechutes, j'ai analysé l'architecture et l'évolution clonales des tumeurs. J’ai ainsi identifié 2 profils évolutifs distincts gouvernant les rechutes précoces et tardives: d'un côté, une dynamique élevée alimentée par un dysfonctionnement des mécanismes de réparation de l'ADN et conduisant à l'émergence rapide de clones mieux adaptés – de l'autre, une dynamique réduite, quasi-inerte, suggérant l'échappement de cellules en dormance épargnée par la chimiothérapie. De manière générale, cette thèse a permis de contribuer à la caractérisation des déterminants génomiques qui constituent la variabilité inter- et intra-tumorale, participent au processus leucémogène et/ou aux mécanismes de résistance au traitement. Ces nouvelles connaissances contribueront à un raffinement de la stratification des patients et leur prise en charge personnalisée. / Acute lymphoblastic leukemia (ALL) is a complex disease with a multi-factorial etiology. It represents the most frequent pediatric cancer and despite a significant increase of survival rate, about 15% of the patients still do not respond to current treatment protocols and over 2/3 of survivors experience long-term treatment related side effects. To reduce these numbers, a better understanding of the underlying causes of ALL is needed. Through the analysis of next-generation sequencing (NGS) data obtained from the established Quebec cALL (QcALL) cohort of the Sainte-Justine hospital, I have been particularly concerned about the genomic determinants that contribute to different phases of ALL (predispositions, onset/progress and relapses). First, I developed an analysis tool (SNooPer) based on a machine learning algorithm integrating both normal and tumor NGS data of the patient to identify somatic mutations from low-pass sequencing. This tool, combined to in silico predictive analysis and to adequate functional validations, allowed us to characterize rare or recurrent events involved in the leukemogenesis process. Through the analysis of pre-B ALLs, I have been able to identify several rare driver genes which had never been associated to ALL before (ACD, DOT1L, HCFC1). The functional study of the identified mutation in ACD, a member of the shelterin complex, showed a concomitant lengthening of the telomeres and decreased apoptosis levels in leukemia cells. Besides the interest aroused by the discovery of these new drivers, I wanted to demonstrate the importance of low-frequency somatic events to establish the generally underestimated interindividual specificity and identify all cellular functions involved. During this work, I also identified new recurrent driver events in T-cell ALL (T-ALL), particularly among poorly characterized immature T-ALL patients. For example, I demonstrated the impact of a recurrent mutation in U2AF1, member of the spliceosome, on alternative splicing of cancer-relevant genes, further suggesting the importance of aberrant splicing in leukemogenesis. I also identified two new X-linked tumor suppressors, MED12 and USP9X, never associated to T-ALL before and obtained results supporting a potential role for these genes in the male-biased sex ratio observed in T-ALL (ratio male:female =1.22). Finally, through the longitudinal study of pre-B cALLs who suffered one or multiple relapses, I analyzed the clonal architecture and evolution of the tumors. I identified two distinct evolution patterns governing either early or late relapses: on one hand a highly dynamic pattern, sustained by a defect of DNA repair processes, illustrating the quick emergence of fitter clones - and on the other hand, a quasi-inert evolution pattern suggesting the escape from dormancy of neoplastic stem cells likely spared from initial cytoreductive therapy. Overall, this thesis contributed to the characterization of genomic determinants that constitute the inter- and intra-tumor variability, participate in leukemogenesis and/or in resistance mechanisms. This new knowledge will contribute to refine patient stratification and treatment.