Genomes provide windows into the evolutionary histories of species. The recent accessibility of genome-scale data in non-model organisms and the proliferation of powerful statistical models are now providing unprecedented opportunities to uncover evolutionary relationships and to test hypotheses about the processes that generate and maintain biodiversity. This dissertation work reveals shallow-scale species boundaries and population genetic structure in two imperiled groups of salamanders and demonstrates that the number and information content of genomic regions used in species delimitation exert strong effects on the resulting inferences. Genome scans are employed to test hypotheses about the mechanisms of genetic sex determination in cryptobranchid salamanders, suggesting a conserved system of female heterogamety in this group. At much deeper scales, phylogenetic analyses of hundreds of protein-coding genes across all major amphibian lineages are employed to reveal the backbone topology and evolutionary timescales of the amphibian tree of life, suggesting a new set of hypotheses for relationships among extant amphibians. Yet, genomic data on their own are no panacea for the thorniest questions in evolutionary biology, and this work also demonstrates the power of a model testing framework to dissect support for different phylogenetic and population genetic hypotheses across different regions of the genome.

Drug repositioning identifies new indications for known drugs. Here we report repositioning of the malaria drug amodiaquine as a potential anti-cancer agent. While most repositioning efforts emerge through serendipity, we have devised a computational approach, which exploits interaction patterns shared between compounds. As a test case, we took the anti-viral drug brivudine (BVDU), which also has anti-cancer activity, and defined ten interaction patterns using our tool PLIP. These patterns characterise BVDU’s interaction with its target s. Using PLIP we performed an in silico screen of all structural data currently available and identified the FDA approved malaria drug amodiaquine as a promising repositioning candidate. We validated our prediction by showing that amodiaquine suppresses chemoresistance in a multiple myeloma cancer cell line by inhibiting the chaperone function of the cancer target Hsp27. This work proves that PLIP interaction patterns are viable tools for computational repositioning and can provide search query information from a given drug and its target to identify structurally unrelated candidates, including drugs approved by the FDA, with a known safety and pharmacology profile. This approach has the potential to reduce costs and risks in drug development by predicting novel indications for known drugs and drug candidates.

A árvore de sufixos é uma estrutura dados, que representa em espaço linear todos os fatores de uma palavra, com diversos exemplos de aplicações práticas. Neste trabalho, definimos uma estrutura mais geral: a árvore de Ukkonen. Provamos para ela diversas propriedades combinatórias, dentre quais, a minimalidade em um sentido preciso. Acreditamos que a apresentação aqui oferecida, além de mais geral que as árvores de sufixo, tem a vantagem de oferecer uma descrição explícita da topologia da árvore, de seus vértices, arestas e rótulos, o que não vimos em nenhum outro trabalho. Como aplicações, apresentamos também a árvore esparsa de sufixos (que armazena apenas um subconjunto dos sufixos) e a árvore de k-fatores (que armazena apenas os segmentos de comprimento k, ao invés dos sufixos) definidas como casos particulares das árvores de Ukkonen. Propomos para as árvores esparsas um novo algoritmo de construção com tempo O(n) e espaço O(m), onde n é tamanho da palavra e m é número de sufixos. Para as árvores de k-fatores, propomos um novo algoritmo online com tempo e espaço O(n), onde n é o tamanho da palavra. / The suffix tree is a data structure that represents, in linear space, all factors of a given word, with several examples of practical applications. In this work, we define a more general structure: the Ukkonen\'s tree. We prove many properties for it, among them, its minimality in a precise sense. We believe that this presentation, besides being more general than the suffix trees, has the advantage of offering an explicit description of the tree topology, its vertices, edges and labels, which was not seen in any other work. As applications, we also presents the sparse suffix tree (which stores only a subset of the suffixes) and the k-factor tree (which stores only the substrings of length k, instead of the suffixes), both defined as Ukkonen\'s tree special cases. We propose a new construction algorithm for the sparse suffix trees with time O(n) and space O(m), where n is the size of the word and m is the number of suffixes. For the k-factor trees, we propose a new online algorithm with time and space O(n), where n is the size of the word.

La maladie de Huntington est une maladie neurodégénérative héréditaire qui est devenue un modèle d'étude pour comprendre la physiopathologie des maladies du cerveau associées à la production de protéines mal conformées et à la neurodégénérescence. Bien que plusieurs mécanismes aient été mis en avant pour cette maladie, dont plusieurs seraient aussi impliqués dans des pathologies plus fréquentes comme la maladie d’Alzheimer ou la maladie de Parkinson, nous ne savons toujours pas quels sont les mécanismes ou les profils moléculaires qui déterminent fondamentalement la dynamique des processus de dysfonction et de dégénérescence neuronale dans cette maladie. De même, nous ne savons toujours pas comment le cerveau peut résister aussi longtemps à la production de protéines mal conformées, ce qui suggère en fait que ces protéines ne présentent qu’une toxicité modérée ou que le cerveau dispose d'une capacité de compensation et de résilience considérable. L'hypothèse de mon travail de thèse est que l'intégration de données génomiques et transcriptomiques au travers des modèles qui récapitulent différentes phases biologiques de la maladie de Huntington peut permettre de répondre à ces questions. Dans cette optique, l'utilisation des réseaux de gènes et la mise en application de concepts issus de la théorie des graphes sont particulièrement bien adaptés à l'intégration de données hétérogènes, au travers des modèles et au travers des espèces. Les résultats de mon travail suggèrent que l'altération précoce (avant les symptômes, avant la mort cellulaire) et éventuellement dès le développement cérébral) des grandes voies de développement et de maintenance neuronale, puis la persistance voire l'aggravation de ces effets, sont à la base des processus physiopathologiques qui conduisent à la dysfonction puis à la mort neuronale. Ces résultats permettent aussi de prioriser des gènes et de générer des hypothèses fortes sur les cibles thérapeutiques les plus intéressantes à étudier d'un point de vue expérimental. En conclusion, mes recherches ont un impact à la fois fondamental et translationnel sur l'étude de la maladie de Huntington, permettant de dégager des méthodes d'analyse et des hypothèses qui pourraient avoir valeur thérapeutique pour les maladies neurodégénératives en général. / Huntington’s disease is a hereditary neurodegenerative disease that has become a model to understand physiopathological mechanisms associated to misfolded proteins that ocurs in brain diseases. Despite exciting findings that have uncover pathological mechanisms occurring in this disease and that might also be relevant to Alzheimer’s disease and Parkinson’s disease, we still do not know yet which are the mechanisms and molecular profiles that rule the dynamic of neurodegenerative processes in Huntington’s disease. Also, we do not understand clearly how the brain resist over such a long time to misfolded proteins, which suggest that the toxicity of these proteins is mild, and that the brain have exceptional compensation capacities. My work is based on the hypothesis that integration of ‘omics’ data from models that depicts various stages of the disease might be able to give us clues to answer these questions. Within this framework, the use of network biology and graph theory concepts seems particularly well suited to help us integrate heterogeneous data across models and species. So far, the outcome of my work suggest that early, pre-symptomatic alterations of signaling pathways and cellular maintenance processes, and persistency and worthening of these phenomenon are at the basis of physiopathological processes that lead to neuronal dysfunction and death. These results might allow to prioritize targets and formulate new hypotheses that are interesting to further study and test experimentally. To conclude, this work shall have a fundamental and translational impact to the field of Huntington’s disease, by pinpointing methods and hypotheses that could be valuable in a therapeutic perspective.

Les sources intrinsèques d'héterogénéité cellulaire, comme l'expression stochastique des gènes, sont de plus en plus reconnues comme jouant un rôle important dans la dynamique des tissus, tumeurs, communautés microbiennes... Cependant, elles sont souvent ignorées ou représentées de manière simpliste dans les modèles théoriques de populations de cellules. Dans cette thèse, nous proposons une approche cellule-centrée (chaque cellule est représentée de manière individuelle), multi-échelle (les décisions cellulaires sont placées sous le contrôle de voies de signalisation biochimiques simulées dans chaque cellule) pour modéliser la dynamique de populations de cellules. La nouveauté principale de cette approche réside dans la prise en compte systématique (pour toutes les protéines modélisées) des fluctuations du niveau des protéines résultant de l'expression stochastique des gènes. Cela permet d'étudier l'effet combiné des causes intrinsèques et environnementales d'héterogénéité cellulaire sur la dynamique de la population de cellules. Un élément central de notre approche est une stratégie parsimonieuse pour attribuer les paramètres de modèles d'expression stochastique des gènes. Nous appliquons cette approche à deux cas d'étude. Nous considérons en premier la resistance à l'agent anti-cancer TRAIL, qui peut induire l'apoptose sélectivement dans les cellules cancéreuses. Nous construisons d'abord un modèle 'cellule unique' de l'apoptose induite par TRAIL et le comparons à des données existantes quantitatives et 'cellules uniques'. Le modèle explique la mort fractionnelle (le fait que seul une fraction des cellules meurent à la suite d'un traitement) et prédit correctement l'héritabilité transiente du destin cellulaire ainsi que l'acquisition transiente de résistance, deux propriétés observées mais hors de portée des modèles pré-existants, qui ne capturent pas la dynamique de l'héterogénéité cellulaire. Dans une seconde étape, nous intégrons ce modèle dans des simulations multi-cellulaires pour étudier la résistance à TRAIL dans des scénarios virtuels intermédiaires entre les études classiques in-vitro et la réponse de tumeurs in-vivo. Plus précisément, nous considérons la réponse en temps long de sphéroides multi-cellulaires à des traitements répétés de TRAIL. L'analyse de nos simulations permet de proposer une explication originale et méchanistique de l'acquisition transiente de résistance, impliquant la dégradation ciblée des protéines activées et un différentiel dans le renouvellement des protéines pro- et anti- apoptotiques. Nous appliquons aussi notre approche à un système synthétique de création de motifs développé dans des levures par des collaborateurs. Nous nous concentrons d'abord sur un circuit senseur d'une molécule messager pour lequel nous construisons un modèle cellule unique qui capture de manière fine la dynamique de réponse du circuit telle qu'observée par cytométrie en flux. Nous intégrons ensuite ce modèle dans des des simulations multi-cellulaires et montrons que la réponse de micro-colonies organisées spatialement et soumises à des gradients de molécule messager est correctement prédite. Finalement, nous incorporons un modèle d'un circuit de mort et comparons les motifs prédits de cellules mortes/vivantes avec des données expérimentales, nous permettons de mieux comprendre comment les paramètres du circuit se traduisent en phénotypes d'organisation multi-cellulaire. Notre approche peut contribuer à l'obtention de modèles de populations de cellules de plus en plus quantitatifs, prédictifs et qui englobent l'échelle moléculaire. / Cell-intrinsic, non-environmental sources of cell-to-cell variability, such as stochastic gene expression, are increasingly recognized to play an important role in the dynamics of tissues, tumors, microbial communities... However, they are usually ignored or oversimplified in theoretical models of cell populations. In this thesis, we propose a cell-based (each cell is represented individually), multi-scale (cellular decisions are controlled by biochemical reaction pathways simulated in each cell) approach to model the dynamics of cell populations. The main novelty compared to traditional approaches is that the fluctuations of protein levels driven by stochastic gene expression are systematically accounted for (i.e., for every protein in the modeled pathways). This enables to investigate the joint effect of cell-intrinsic and environmental sources of cell-to-cell variability on cell population dynamics. Central to our approach is a parsimonious and principled parameterization strategy for stochastic gene expression models. The approach is applied on two case studies. First, it is used to investigate the resistance of HeLa cells to the anti-cancer agent TRAIL, which can induce apoptosis specifically in cancer cells. A single-cell model of TRAIL-induced apoptosis is constructed and compared to existing quantitative, single-cell experimental data. The model explains fractional killing and correctly predicts transient cell fate inheritance and reversible resistance, two observed properties that are out of reach of previous models of TRAIL-induced apoptosis, which do not capture the dynamics of cell-to-cell variability. In a second step, we integrate this model into multi-cellular simulations to study TRAIL resistance in virtual scenarios constructed to help bridging the gap between standard in-vitro assays and the response of in-vivo tumors. More precisely, we consider the long-term response of multi-cellular spheroids to repeated TRAIL treatments. Analysis of model simulations points to an novel, mechanistic explanation for transient resistance acquisition, which involves the targeted degradation of activated proteins and a differential turnover between pro- and anti- apoptotic proteins. Second, we apply our approach to a synthetic spatial patterning system in yeast cells developed by collaborators. Focusing first on a sensing circuit responding to a messenger molecule, we construct a single-cell model that accurately capture the response kinetics of the circuit as observed in flow cytometry data. We then integrate this model into multi-cellular simulations and show that the response of spatially-organized micro-colonies submitted to gradients of messenger molecules is correctly predicted. Finally, we incorporate a model of a killing circuit and compare the predicted patterns of dead or alive cells with experimental data, yielding insights into how the circuit parameters translate into multi-cellular organization phenotypes. Our modeling approach has the potential to accelerate the obtention of more quantitative and predictive models of cell populations that encompass the molecular scale.

Le métabolisme définit l’ensemble des réactions biochimiques au sein d’un organisme, lui permettant de survivre et de s’adapter dans différents environnements. La régulation de ces réactions requiert un processus complexe impliquant de nombreux effecteurs interagissant ensemble à différentes échelles.Développer des modèles de ces réseaux de régulation est ainsi une étape indispensable pour mieux comprendre les mécanismes précis régissant les systèmes vivants et permettre, à terme, la conception de systèmes synthétiques, autorégulés et adaptatifs, à l'échelle du génome. Dans le cadre de ces travaux interdisciplinaires, nous proposons d’utiliser une approche itérative d’inférence de réseau et d’interrogation afin de guider l’ingénierie du métabolisme de la levure d’intérêt industriel Yarrowia lipolytica.À partir de données transcriptomiques, le premier réseau de régulation de l’adaptation à la limitation en azote et de la production de lipides a été inféré pour cette levure. L’interrogation de ce réseau a ensuite permis de mettre en avant et valider expérimentalement l’impact de régulateurs sur l'accumulation lipidique.Afin d’explorer davantage les liens entre régulation et métabolisme, une nouvelle méthode, CoRegFlux, a été proposée pour la prédiction de phénotype métabolique à partir des profils d’activités des régulateurs dans les conditions étudiées.Ce package R, disponible sur la plateforme Bioconductor, a ensuite été utilisé pour mieux comprendre l’adaptation à la limitation en azote et identifier des phénotypes d’intérêts en vue de l’ingénierie de cette levure, notamment pour la production de lipides et de violacéine.Ainsi, par une approche itérative, ces travaux apportent de nouvelles connaissances sur les interactions entre la régulation et le métabolisme chez Y. lipolytica, l’identification de motifs de régulation chez cette levure et contribue au développement de méthodes intégratives pour la conception de souches assistée par ordinateur. / Metabolism defines the set of biochemical reactions within an organism, allowing it to survive and adapt to different environments. Regulating these reactions requires complex processes involving many effectors interacting together at different scales.Developing models of these regulatory networks is therefore an essential step in better understanding the precise mechanisms governing living systems and ultimately enabling the design of synthetic, self-regulating and adaptive systems at the genome level. As part of this interdisciplinary work, we propose to use an iterative network inference and interrogation approach to guide the engineering of the metabolism of the yeast of industrial interest Yarrowia lipolytica.Based on transcriptomic data, the first network for the regulation of adaptation to nitrogen limitation and lipid production in this yeast was inferred.The interrogation of this network has then allowed to to highlight and experimentally validate the impact of several regulators on lipid accumulation. In order to further explore the relationships between regulation and metabolism, a new method, CoRegFlux, has been proposed for the prediction of metabolic phenotype based on the influence profiles of regulators in the studied conditions. This R package, available on the Bioconductor platform, was then used to better understand adaptation to nitrogen limitation and to identify phenotypes of interest for strain engineering, particularly for the production of lipids and amino acid derivatives such as violacein.Thus, through an iterative approach, this work provides new insights into the interactions between regulation and metabolism in Y. lipolytica, conserved regulatory module in this yeast and contributes to the development of innovative integrative methods for computer-assisted strain design.

Drug repositioning identifies new indications for known drugs. Here we report repositioning of the malaria drug amodiaquine as a potential anti-cancer agent. While most repositioning efforts emerge through serendipity, we have devised a computational approach, which exploits interaction patterns shared between compounds. As a test case, we took the anti-viral drug brivudine (BVDU), which also has anti-cancer activity, and defined ten interaction patterns using our tool PLIP. These patterns characterise BVDU’s interaction with its target s. Using PLIP we performed an in silico screen of all structural data currently available and identified the FDA approved malaria drug amodiaquine as a promising repositioning candidate. We validated our prediction by showing that amodiaquine suppresses chemoresistance in a multiple myeloma cancer cell line by inhibiting the chaperone function of the cancer target Hsp27. This work proves that PLIP interaction patterns are viable tools for computational repositioning and can provide search query information from a given drug and its target to identify structurally unrelated candidates, including drugs approved by the FDA, with a known safety and pharmacology profile. This approach has the potential to reduce costs and risks in drug development by predicting novel indications for known drugs and drug candidates.

The following contains two projects focused on the fungal pathogen, Fusarium oxysporum. The first project was purely computational in the examination of transposable elements (TEs), which are mobile sequences with the ability to multiply and move in their host genome. In F. oxysporum, TEs such as miniature impala elements are associated with the secreted in xylem gene that are related to its virulence over its host. The F. oxysporum species complex can be utilized as a model system for the examination of TE content and TE expression during the infection cycle. To find whether TEs play a role in the infection process and if their expression changes when fungi are in planta, a comparison was made using RNA-seq data from a pathogenic (Fo5176) and a non-pathogenic strain (Fo47) of F. oxysporum interacting with the model plant Arabidopsis thaliana. Complementary to this, the copy numbers of the same TEs were calculated in the two aforementioned strains and in F. oxysporum f.sp. lycopersici 4287 (Fo4287) to find if there was a correlation between expression and copy number. Using these two different datasets together showed that TE expression and copy number are lower in the non-pathogenic strain and unlinked in the infection course. The second project examined the growth inhibition of Fusarium oxysporum isolates Fo32931 (the isolate pathogenic to immunocompromised humans) and Fo4287 with the use of extracts from chilies of Capsicum chinense. Pepper plants were grown from seed and the peppers were harvested for an ethanol (100%) extraction. After preparation, the optical density of growth of the F. oxysporum isolates was measured for a 48-hour period with 96-well plate containing varying concentrations of the extracts and controls. Growth curves were analyzed and normalized to a growth control. After doing High Performance Liquid Chromatography, an estimated concentration of capsaicin (the causal agent of the burning sensation from hot chilis) was established. A correlation between the amount of growth inhibition and the concentration of capsaicin was made. Taken together, the data suggests that an increase of capsaicin concentration in extracts is correlated with reduced growth for the two tested isolates of F. oxysporum.

<p>Data science uses the latest techniques in statistics and machine learning to extract insights from data. With the increasing amount of protein data, a number of novel research approaches have become feasible.</p><p>Micropeptides are an emerging field in the protein universe. They are small proteins with <= 100 amino acid residues (aa) and are translated from small open reading frames (sORFs) of <= 303 base pairs (bp). Traditionally, their existence was ignored because of the technical difficulties in isolating them. With technological advances, a growing number of micropeptides have been characterized and shown to play vital roles in many biological processes. Yet, we lack bioinformatics methods for predicting them directly from DNA sequences, which could substantially facilitate research in this field with minimal cost. With the increasing amount of data, developing new methods to address this need becomes possible. We therefore developed MiPepid, a machine-learning-based method specifically designed for predicting micropeptides from DNA sequences by curating a high-quality dataset and by training MiPepid using logistic regression with 4-mer features. MiPepid performed exceptionally well on holdout test sets and performed much better than existing methods. MiPepid is available for downloading, easy to use, and runs sufficiently fast.</p><p>Long noncoding RNAs (LncRNAs) are transcripts of > 200 bp and does not encode a protein. Contrary to their “noncoding” definition, an increasing number of lncRNAs have been found to be translated into functional micropeptides. Therefore, whether most lncRNAs are translated is an open question of great significance. To address this question, by harnessing the availability of large-scale human variation data, we have explored the relationships between lncRNAs, micropeptides, and canonical regular proteins (> 100 aa) from the perspective of genetic variation, which has long been used to study natural selection to infer functional relevance. Through rigorous statistical analyses, we find that lncRNAs share a similar genetic variation profile with proteins regarding single nucleotide polymorphism (SNP) density, SNP spectrum, enrichment of rare SNPs, etc., suggesting lncRNAs are under similar negative selection strength with proteins. Our study revealed similarities between micropeptides, lncRNAs, and canonical proteins and is the first attempt to explore the relationships between the three groups from a genetic variation perspective.</p><p>Deep learning has been tremendously successful in 2D image recognition. Protein binding ligand prediction is fundamental topic in protein research as most proteins bind ligands to function. Proteins are 3D structures and can be considered as 3D images. Prediction of binding ligands of proteins can then be converted to a 3D image classification problem. In addition, a large number of protein structure data are available now. We therefore utilized deep learning to predict protein binding ligands by designing a 3D convolutional neural network from scratch and by building a large 3D image dataset of protein structures. The trained model achieved an average F1 score of over 0.8 across 151 classes on the holdout test set. Compared to existing methods, our model performed better. In summary, we showed the feasibility of deploying deep learning in protein structure research.</p><p>In conclusion, by exploring various edges of the protein universe from the perspective of data science, we showed that the increasing amount of data and the advancement of data science methods made it possible to address a wide variety of pressing biological questions. We showed that for a successful data science study, the three components – goal, data, method – all of them are indispensable. We provided three successful data science studies: the careful data cleaning and selection of machine learning algorithm lead to the development of MiPepid that fits the urgent need of a micropeptide prediction method; identifying the question and exploring it from a different angle lead to the key insight that lncRNAs resemble micropeptides; applying deep learning to protein structure data lead to a new approach to the long-standing question of protein-ligand binding. The three studies serve as excellent examples in solving a wide range of data science problems with a variety of issues.</p>

Proteins are involved in almost all functions in a living cell, and functions of proteins are realized by their tertiary structures. Protein three-dimensional structures can be solved by multiple experimental methods, but computational approaches serve as an important complement to experimental methods for comparing and analyzing protein structures. Protein structure comparison allows the transfer of knowledge about known proteins to a novel protein and plays an important role in function prediction. Obtaining a global perspective of the variety and distribution of protein structures also lays a foundation for our understanding of the building principle of protein structures. This dissertation introduces our computational method to compare protein 3D structures and presents a novel mapping of protein shapes that represents the variety and the similarities of 3D shapes of proteins and their assemblies. The methods developed in this work can be applied to obtain new biological insights into protein atomic structures and electron density maps.