Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. If one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. All such safe walks were recently characterized as omnitigs, leading to the first safe and complete genome assembly algorithm. Even if omnitig finding was improved to quadratic time, it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We describe an O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ(mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig, with two consequences: a linear-time output sensitive algorithm enumerating all maximal omnitigs and a compact O(m) representation of all maximal omnitigs. This safe and complete genome assembly algorithm was followed by other works improving the time bounds, as well as extending the results for different notions of assembly solution. But it remained open whether one can be complete also for models of genome assembly of practical applicability. In this dissertation, we also present a universal framework for obtaining safe and complete algorithms which unify the previous results, while also allowing to characterize different assembly problems. This is based on a novel graph structure, called the hydrostructure of a walk, which highlights the reachability properties of the graph from the perspective of the walk. Almost all of our characterizations are directly adaptable to optimal verification algorithms, and simple enumeration algorithms. Most of these algorithms are also improved to optimality using an incremental computation procedure and a previous optimal algorithm of a specific model.

Cette thèse vise à étudier certains modèles biologiques dans le réseau neuronal et dans la chimiotaxie avec la méthode d’analyse spectrale. Afin de traiter les principaux problèmes, tels que l’existence et l’unicité des solutions et des états stationnaires ainsi que les comportements asymptotiques, le modèle linéaire ou linéarisé associé est considéré par l’aspect du spectre et des semi-groupes dans les espaces appropriés, puis la stabilité de modèle non linéaire suit. Plus précisément, nous commençons par une équation de courses-et-chutes linéaire dans la dimension d≥1 pour établir l’existence d’un état stationnaire unique, positif et normalisé et la stabilité exponentielle asymptotique dans l’espace L¹ pondéré basé sur la théorie de Kerin-Rutman avec quelques estimations du moment de la théorie cinétique. Ensuite, nous considérons le modèle du temps écoulé sous les hypothèses générales sur le taux de tir et nous prouvons l’unicité de l’état stationnaire et sa stabilité exponentielle non linéaire en cas sans ou avec délai au régime de connectivité faible de la théorie de l’analyse spectrale pour les semi-groupes. Enfin, nous étudions le modèle sous une hypothèse de régularité plus faible sur le taux de tir et l’existence de la solution ainsi que la même stabilité exponentielle sont généralement établies n’importe la prise en compte du délai ou non, au régime de connectivité faible ou forte. / This thesis is aimed to study some biological models in neuronal network and chemotaxis with the spectral analysis method. In order to deal with the main concerning problems, such as the existence and uniqueness of the solutions and steady states as well as the asymptotic behaviors, the associated linear or linearized model is considered from the aspect of spectrum and semigroups in appropriate spaces then the nonlinear stability follows. More precisely, we start with a linear runs-and-tumbles equation in dimension d≥1 to establish the existence of a unique positive and normalized steady state and the exponential asymptotic stability in weighted L¹ space based on the Krein-Rutman theory together with some moment estimates from kinetic theory. Then, we consider time elapsed model under general assumptions on the firing rate and prove the uniqueness of the steady state and its nonlinear exponential stability in case without or with delay in the weak connectivity regime from the spectral analysis theory for semigroups. Finally, we study the model under weaker regularity assumption on the firing rate and the existence of the solution as well as the same exponential stability are established generally no matter taking delay into account or not and no matter in weak or strong connectivity regime.