Дисертації з теми "Homologie distante"

L'augmentation toujours plus importante de données génomiques et métagénomiques appelle de nouveaux développements méthodologiques et bio-informatiques, afin de caractériser avec davantage de précision les phénomènes évolutifs dans leur ensemble. En particulier, certaines des méthodes usuelles pour étudier l'évolution des (familles de) gènes s'avèrent inadaptées lorsque la parenté entre séquences n'est que partiellement supportée. Ainsi, la définition et la reconstruction de familles de gènes se heurtent à l'obstacle de l'homologie distante, qui passe sous le seuil de détection des alignements de séquences. De même, les mécanismes d'évolution combinatoire, tels que les fusions et fissions de gènes, remettent en cause les représentations purement arborescentes de l'évolution des familles de gènes. L'application de méthodes complémentaires basées sur les réseaux de similarité de séquences permet de contourner certaines de ces lacunes, en proposant une représentation holistique des similarités entre gènes. La détection et l'analyse d'homologues très divergents de familles de gènes fortement conservées dans des jeux de données environnementaux est notamment facilitée par la recherche itérative d'homologie fondée sur les réseaux. Cette fouille itérative de métagénomes révèle une immense diversité de variants environnementaux dans ces familles, qui divergent de la diversité connue tant par leur séquence que par la structure des protéines qu'ils encodent, et elle permet de suggérer des pistes pour guider de futures explorations de la matière noire microbienne. En outre, en prenant en compte des liens d'homologie partielle entre séquences génétiques, les réseaux de similarité de séquences permettent une identification systématique des évènements de fusion et de fission de gènes. Il devient ainsi possible d'évaluer l'impact de ces processus au cours de l'évolution de lignées biologiques d'intérêt, permettant de comparer le rôle qu'ils ont joué lors de l'émergence de phénotypes multicellulaires complexes dans plusieurs telles lignées. Plus généralement, ces approches basées sur les réseaux illustrent l'intérêt de prendre en compte une pluralité de modèles pour étudier une plus grande variété de processus évolutifs
The ever-increasing accumulation of genomic and metagenomic data calls for new methodological developments in bioinformatics, in order to characterise evolutionary phenomena as a whole with better accuracy. In particular, some of the canonical methods to study the evolution of genes and gene families may be ill-suited when the relatedness of sequences is only partially supported. For instance, the definition and reconstruction of gene families face the hurdle of remote homology, which falls beneath the detection thresholds of sequence alignments. Likewise, combinatorial mechanisms of evolution, such as gene fusion and gene fission, challenge the purely tree-based representations of gene family evolution. The use of complementary methods based on sequence similarity networks allows us to circumvent some of these shortcomings, by offering a more holistic representation of similarities between genes. The detection and analysis of highly divergent homologues of strongly conserved families in environmental sequence datasets, in particular, is facilitated by iterative homology search protocols based on networks. This iterative mining of metagenomes reveals an immense diversity of environmental variants in these families, diverging from the known diversity in primary sequence as well as in the tertiary structure of the proteins they encode. It is thus able to suggest possible directions of future explorations into microbial dark matter. Furthermore, by factoring in relationships of partial homology between gene sequences, sequence similarity networks allow for a systematic identification of gene fusion and fission events. It thus becomes possible to assess the effects of these processes on the evolution of biological lineages of interest, enabling us for instance to compare the role that they played in the emergence of complex multicellular phenotypes between several such lineages. More generally, these network-based approaches illustrate the benefits of taking a plurality of models into account, in order to study a broader range of evolutionary processes

Nous contribuons à l'inférence topologique, basée sur la théorie de l'homologie persistante, en proposant trois familles de filtrations.Nous établissons pour chacune d'elles des résultats de consistance---c'est-à-dire de qualité d'approximation d'un objet géométrique sous-jacent---, et de stabilité---c'est-à-dire que robustesse face à des erreurs de mesures initiales.Nous proposons des algorithmes concrets afin de pouvoir utiliser ces méthodes en pratique.La première famille, les filtrations-DTM, est une alternative robuste à la classique filtration de Cech lorsque le nuage de points est bruité ou contient des points aberrants.Elle repose sur la notion de distance à la mesure qui permet d'obtenir une stabilité au sens de la distance de Wasserstein.Deuxièmement, nous proposons les filtrations relevées, qui permettent d'estimer l'homologie des variétés immergées, même quand leur portée est nulle.Nous introduisons la notion de portée normale, et montrons qu'elle conduit à un contrôle quantitatif de la variété.Nous étudions l'estimation des espaces tangents par les matrices de covariance locale.En troisième lieu, nous développons un cadre pour les filtrations de fibrés vectoriels, et définissons les classes de Stiefel-Whitney persistantes.Nous montrons que les classes persistantes associées aux filtrations de fibrés de Cech sont consistantes et stables en distance de Hausdorff.Pour permettre leur mise en œuvre algorithmique, nous introduisons la notion de condition étoile faible
We contribute to the theory of topological inference, based on the theory of persistent homology, by proposing three families of filtrations.For each of them, we prove consistency results---that is, the quality of approximation of an underlying geometric object---, and stability results---that is, robustness against initial measurement errors.We propose concrete algorithms in order to use these methods in practice.The first family, the DTM-filtration, is a robust alternative to the classical Cech filtration when the point cloud is noisy or contains outliers.It is based on the notion of distance to measure, which allows to obtain stability in the sense of the Wasserstein distance.Secondly, we propose the lifted filtrations, which make it possible to estimate the homology of immersed manifolds, even when their reach is zero.We introduce the notion of normal reach, and show that it leads to a quantitative control of the manifold.We study the estimation of tangent spaces by local covariance matrices.Thirdly, we develop a framework for vector bundle filtrations, and define the persistent Stiefel-Whitney classes.We show that the persistent classes associated to the Cech bundle filtrations are Hausdorff-stable and consistent.To allow their algorithmic implementation, we introduce the notion of weak star condition

L’homologie persistante est un outil fondamental dans la topologie computationnelle. Cette méthode est utilisée pour reconnaître et comparer les formes. Dans ce travail nous étudions d’abord l’homologie persistante dans le cas unidimensionnel d’ordre 0 qu’on appelle aussi fonction de taille. Nous présentons une démonstration du fait que toute fonction de taille peut être représentée comme un ensemble de points et de lignes dans le plan réel, avec des multiplicités. Cela permet une approche algébrique aux fonctions de taille et la construction de nouvelles pseudo distances entre les fonctions de taille pour comparer les formes. Nous calculons ensuite l’homologie persistante unidimensionnelle d’ordre n avec différentes méthodes de filtration de l’espace correspondant à l’histoire d’un complexe croissant. Nous classons un changement topologique qui se produit pendant la croissance soit comme une caractéristique ou un bruit, en fonction de sa durée de vie ou de sa persistance dans la filtration. Une présentation avec des codes barres affiche alors la persistance de ces invariants. L’homologie persistante multidimensionnelle nous permet de soutirer plus d’informations sur les formes en utilisant la fonction de filtration avec des valeurs dans [nombre réel]k. Pour fournir un descripteur de forme concis et complet dans le cas multidimensionnel nous réduisons le calcul de l’homologie persistante multidimensionnelle au calcul de l’homologie persistante ordinaire pour une famille paramétrée de fonctions à valeur dans [nombre réel].

Motivated by the formation of certain link types during Hin-mediated DNA recombination experiments, we consider tangle equations where one of the products is a connect-sum of 2-bridge links. We are thus led to study Dehn surgeries on knots in lens spaces that yield connect-sums of lens spaces. Using 3-manifold methods, we prove, for certain classes of knot exteriors, a distance bound on Dehn surgery slopes. (This proof complements an algebraic-geometric proof of a more general statement due to Boyer and Zhang [6]). Analysing the known examples of connect-sums of lens spaces surgeries, together with some sample calculations, we conjecture that if surgery on a knot K [Symbol appears here. To view, please open pdf attachment] L(p, q), with p, q [Symbol appears here. To view, please open pdf attachment]1, 2, yields L(p, q)#L(t, 1), then the knot has reducible exterior. Using Heegaard Floer homology, we prove a special case of the conjecture, as well as some surgery obstructions. We then apply our results, in the spirit of the tangle model of Ernst and Sumners [67], to the problem of Hin-mediated DNA recombination, where we characterise its distributive recombination step.

In this thesis we present a new result concerning the theory of group invariant persistent homology. This theory adapts persistent homology in the presence of the action on a space of functions Phi of a subgroup G of the group H of all self-homeomorphisms of a topological space X. Its model is based on a space of suitable operators defined on Phi. After describing the mathematical setting and recalling some basic results, we prove that the space of these operators is compact with respect to a suitable topology. In order to prove this result, we require that Phi, G, X are compact.

La commutation isotypique au sein du locus des chaînes lourdes d'immunoglobulines (IgH) nécessite la transcription geffi1inale, l'intervention de AID (Activation-Induced cytidine Deaminase) et des éléments régulateurs en aval du locus (3 'RR). Pour analyser l'effet des interactions de longue distance sur la commutation isotypique, nous avons généré 3 modèles murins par recombinaison homologue. Dans le premier modèle, nous avons inséré un isolateur sauvage ou muté entre la 3'RR et le locus IgH. Dans le deuxième modèle, nous avons inséré un site de polyadénylation et de pause transcriptionnelle en aval des promoteurs germinaux Imu ou de Igamma3 pour un arrêt prématuré de la transcription germinale. Enfin dans le troisième modèle, nous avons remplacé le promoteur Igamma3 par Igamma1. Ces 3 approches nous ont permiis de mieux comprendre les interactions à longue distance au cours de la régulation de la transcription germinale, de la commutation isotypique et de l'élongation transcriptionnelle
Class switch recombination is a process in the immunoglobulin heavy chain locus (IgH) which requires germline transcription, Activated-Induced cytidine Deaminase (AID) and the 3' regulatory region (3'RR). In order to investigate the effect of long-range interactions on the class switch recombination, we generated three models in the mouse thanks to homologous recombination. In the first model, the entire or mutated core element of the chicken HS4 insulator was inserted between the 3'RR and the IgH locus. In the second, a polyadenylation and pause site was inserted downstream of germline promoters Imu or Igamma3 to attempt a premature termination of the germline transcription. In the last, the Igamma3 germline promoter was replaced by Igamma1. Thanks to these models, a better understanding is possible about the long-range interactions during the regulation of the germline transcription, the class switch recombination and the transcriptional elongation

La quantité de données disponibles n'a jamais été aussi grande. Se poser les bonnes questions, c'est-à-dire des questions qui soient à la fois pertinentes et dont la réponse est accessible est difficile. L'analyse topologique de données tente de contourner le problème en ne posant pas une question trop précise mais en recherchant une structure sous-jacente aux données. Une telle structure est intéressante en soi mais elle peut également guider le questionnement de l'analyste et le diriger vers des questions pertinentes. Un des outils les plus utilisés dans ce domaine est l'homologie persistante. Analysant les données à toutes les échelles simultanément, la persistance permet d'éviter le choix d'une échelle particulière. De plus, ses propriétés de stabilité fournissent une manière naturelle pour passer de données discrètes à des objets continus. Cependant, l'homologie persistante se heurte à deux obstacles. Sa construction se heurte généralement à une trop large taille des structures de données pour le travail en grandes dimensions et sa robustesse ne s'étend pas au bruit aberrant, c'est-à-dire à la présence de points non corrélés avec la structure sous-jacente.Dans cette thèse, je pars de ces deux constatations et m'applique tout d'abord à rendre le calcul de l'homologie persistante robuste au bruit aberrant par l'utilisation de la distance à la mesure. Utilisant une approximation du calcul de l'homologie persistante pour la distance à la mesure, je fournis un algorithme complet permettant d'utiliser l'homologie persistante pour l'analyse topologique de données de petite dimension intrinsèque mais pouvant être plongées dans des espaces de grande dimension. Précédemment, l'homologie persistante a également été utilisée pour analyser des champs scalaires. Ici encore, le problème du bruit aberrant limitait son utilisation et je propose une méthode dérivée de l'utilisation de la distance à la mesure afin d'obtenir une robustesse au bruit aberrant. Cela passe par l'introduction de nouvelles conditions de bruit et l'utilisation d'un nouvel opérateur de régression. Ces deux objets font l'objet d'une étude spécifique. Le travail réalisé au cours de cette thèse permet maintenant d'utiliser l'homologie persistante dans des cas d'applications réelles en grandes dimensions, que ce soit pour l'inférence topologique ou l'analyse de champs scalaires
Massive amounts of data are now available for study. Asking questions that are both relevant and possible to answer is a difficult task. One can look for something different than the answer to a precise question. Topological data analysis looks for structure in point cloud data, which can be informative by itself but can also provide directions for further questioning. A common challenge faced in this area is the choice of the right scale at which to process the data.One widely used tool in this domain is persistent homology. By processing the data at all scales, it does not rely on a particular choice of scale. Moreover, its stability properties provide a natural way to go from discrete data to an underlying continuous structure. Finally, it can be combined with other tools, like the distance to a measure, which allows to handle noise that are unbounded. The main caveat of this approach is its high complexity.In this thesis, we will introduce topological data analysis and persistent homology, then show how to use approximation to reduce the computational complexity. We provide an approximation scheme to the distance to a measure and a sparsifying method of weighted Vietoris-Rips complexes in order to approximate persistence diagrams with practical complexity. We detail the specific properties of these constructions.Persistent homology was previously shown to be of use for scalar field analysis. We provide a way to combine it with the distance to a measure in order to handle a wider class of noise, especially data with unbounded errors. Finally, we discuss interesting opportunities opened by these results to study data where parts are missing or erroneous

L'applicazione di operatori non espansivi equivarianti rispetto a un gruppo (GENEOs) in ambito di deep learning e topological data analysis si è recentemente dimostrata molto efficace. In questa tesi viene approfondito il concetto di permutante, su cui si basa un metodo di costruzione di tali operatori. In particolare si dimostra che i permutanti sono organizzati in una struttura reticolare, dotata di massimo, e che quest'ultimo risulta essere un gruppo.

In questa tesi vengono illustrati metodi di topologia computazionale negli ambiti di topological data analysis e shape comparison. Nello specifico, dato uno spazio topologico X e un sottogruppo G di Homeo(X), viene studiato un set di dati Φ composto da funzioni definite su X, continue e limitate, a valori reali. Per farlo si utilizzano degli operatori G-invarianti non espansivi (GINO), che si sono dimostrati efficaci per approssimare la pseudo-distanza naturale. In particolare in questo lavoro vengono studiati metodi per la costruzione di tali operatori, sfruttando le proprietà algebriche delle variabili del problema. È importante osservare che il gruppo G viene sempre considerato come variabile, in quanto un cambio dell’osservatore può generalmente coincidere con un cambio dell’invarianza a cui si è interessati.

La modélisation statistique de séquences homologues par HMM profils laisse de côté l'information phylogénétique reliant les séquences. Nous proposons ici des modèles combinant efficacement analyse longitudinale (séquences protéiques vues comme des enchaînements d'acides aminés) et verticale (séquences vues comme étant le produit d'une évolution le long des branches d'un arbre phylogénétique). De tels modèles appartiennent à la famille des phylo-HMM, introduite dans le courant des années 1990 (Mitchison& Durbin). Notre objectif étant la détection d'homologues distants dans les bases de données, nous décrivons une méthodologie de dérivation complète des paramètres des phylo-HMM profils basée sur la phylogénie: les modèles que nous proposons sont des HMM de reconstruction ancestrale,issus d'un processus d'inférence phylogénétique des positions conservées, des probabilités d'émission de caractères sur les états Match et Insertion, ainsi que des probabilités de transition entre états du HMM. Nous suggérons notamment une nouvelle modélisation pour l'évolution des transitions entre états du HMM, ainsi qu'un modèle de type Ornstein-Uhlenbeck pour l'évolution des longueurs des insertions. Contraintes évolutives et contraintes longitudinales sont ainsi simultanément prises en compte. Le processus d'apprentissage développé a été implémenté et testé sur une base de données de familles de séquences homologues,mettant en évidence des gains à la fois en termes de vraisemblance accrue des homologues distants et en termes de performance lorsqu'il s'agit de détecter ceux-ci dans les grandes bases de données protéiques

碩士
國立交通大學
生物資訊研究所
92
The RDHSP (Recognize Distant Homologues by Sequence-struc- ture Profile com- parison) is the protein fold recognition using the threading method. For a given target protein seq- uence and a template structure, RDHSP guarantees to find a globally optimal threading alignment between the two. RDHSP is based upon the premise that structure is better conserv- ed than sequence. Every residue in a protein tertiary stru- cture exists in a particular environment that can be descr- ibed by features such as main-chain conform- ation, solvent accessibility, and contact energy, contact residue numbers. RDHSP empl- oys environment-specific scoring table that of- fer a more precise and discriminating measure of substitut- ion probabilities. Compare with the popular PSI-BLAST, RDHSP is 4.6%, 22.2% and 21.6% more sensitive in detecting the family, superfamily, fold simila- rities in the Lindal benchmark.