Graph Theoretical Problems in Life Sciences

Nikolai Nøjgaard

Graph Theoretical Problems in Life Sciences

Nikolai Nøjgaard^*

^*Kontaktforfatter

Institut for Matematik og Datalogi

Publikation: Afhandling › Ph.d.-afhandling

Abstract

En vigtig opgave i naturvidenskab er at beskrive, karakteriserer, og udlede relationer mellem diskrete objekter. Et set a relationer E på et set af objekter V kan beskrives naturligt som en graf G = ¹V; Eº. Det er derfor ofte praktisk at formalisere problemer i naturvidenskab som graf teoretiske problemer. I denne afhandling, vil vi beskrive et antal af problemer der kan blive fundet i specifikt biovidenskab, og vise hvordan graf teoretiske koncepter kan bruges til at formalisere og løse de præsenteret problemer. Indholdet af denne afhandling er en række af artikler, der alle løser et separat problem, der er relevant for biologi eller biokemi.

Den første artikel undersøger problemer fundet i selvsamlende protein design. Det viser sig at design af polypeptider bestående af sammensatte coiled coil segmenter der samler sig til polyhedra, er tæt forbundet med konceptet om 1-face embeddings i graf topologi. Vi viser at 1-face embeddings kan blive kanoniseret i lineær tid, og vi præsenterer algoritmer for at enemurere ikke isomorfiske 1-face embeddings i orienterbare overflader.

Den anden og tredje artikel undersøger problemer fundet i evolutionær biologi. I særdeleshed fokuserer de på at udlede gen og arts træer direkte fra sekvens data uden nogen a priori viden om træernes topologi. Den anden artikel karakteriserer hvornår gen træer kan blive udledt fra delvis estimeret ortologi, paralogi, og xenologi relationer. Ved brug af denne karakterisering, bygger vi en algoritme der kan konstruerer gen træer konsistent med de givne estimater i polynomiel tid, hvis et træ eksisterer. Den præsenteret algoritme er brugt til at vise at gen træer kan blive nøjagtigt udledt selv hvis kun 20% af relationerne er kendt. Den tredje artikel undersøger hvordan vi kan rekonciliere gen og arts træer i en biologisk mulig måde, når vi kender begivenhederne af gen træet. Biologisk mulige rekoncilieringer er karakteriseret således at de kun afhænger af topologien for et givet arts og gen træ. Ved brug af denne karakterisering bygger vi en algoritme der konstruerer en biologisk mulig rekonciliering mellem et arts og gen træ i polynomiel tid, hvis sådan en rekonciliering eksisterer.

Den fjerde og femte artikel er bekymrede med at analysere automatisk genereret reaktions netværker. Den fjerde artikel indføre en algoritme til at forudsige termodynamiske egenskaber af molekyler i en kunstig kemi. Algoritmen er baseret på den velkendte group contribution method og vil automatisk udlede funktionelle grupper baseret på fælles strukturelle motiver fundet i en samplet set af molekyler. Det er vist eksperimentelt, at algoritmen kan nøjagtigt forudsige en bred vifte af molekylære egenskaber såsom normalt kogepunkt, Gibbs fri energi, og minimum fri energi for RNA sekundære strukturer. Den femte og sidste artikel præsenterer et fundament for at følge atomer gennem reaktions netværker genereret fra en graf grammatik. Artiklen definerer den karakteristiske monoid for et reaktions netværk, ved brug af koncepter fundet i semigruppe teori. Den viser hvordan naturlige subsystemer af et reaktions netværk organisk opstår fra den højre Cayley graf af den karakteristiske monoid. Anvendeligheden af de præsenteret metoder er vist ved først at anvende dem til at designe isotopic labeling eksperimenter, og derefter ved at anvende dem til at analyserer TCA cyklen.

Originalsprog	Engelsk
Bevilgende institution	Syddansk Universitet
Vejledere/rådgivere	Merkle, Daniel, Vejleder Hellmuth, Marc, Vejleder, Ekstern person
Udgiver	Syddansk Universitet. Det Naturvidenskabelige Fakultet
Status	Udgivet - apr. 2020

Note vedr. afhandling

Afhandlingen kan læses på SDUs bibliotek.

5 Konferencebidrag i proceedings

Generic Context-Aware Group Contributions
Flamm, C., Hellmuth, M., Merkle, D., Nojgaard, N. & Stadler, P. F., 2022, IEEE/ACM Transactions on Computational Biology and Bioinformatics. 1 udg. IEEE, Bind 19. s. 429-442 (IEEE/ACM Transactions on Computational Biology and Bioinformatics).
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Åben adgang
Fil
70 Downloads (Pure)
Atom Tracking Using Cayley Graphs
Hellmuth, M., Merkle, D. & Nøjgaard, N., 2020, Proceedings of Bioinformatics Research and Applications: 16th International Symposium, ISBRA 2020. Cai, Z., Mandoiu, I., Narasimhan, G., Skums, P. & Guo, X. (red.). Springer, s. 406-415 (Lecture Notes in Computer Science; Nr. 12304).
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review
Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings
Hellmuth, M., Knudsen, A. S., Kotrbík, M., Merkle, D. & Nøjgaard, N., 2018, 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. Venkatasubramanian, S. & Pagh, R. (red.). Society for Industrial and Applied Mathematics, s. 154-168
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Citationsformater

@misc{8986c3cd4c7945d3bee6727d74ca1849,

title = "Graph Theoretical Problems in Life Sciences",

abstract = "A common task in natural sciences is to describe, characterize, and infer relations between discrete objects. A set of relations E on a set of objects V can naturally be expressed as a graph G = ¹V; Eº. It is therefore often convenient to formalize problems in natural sciences as graph theoretical problems. In this thesis we will examine a number of problems found in life sciences in particular, and show how to use graph theoretical concepts to formalize and solve the presented problems. The content of the thesis is a collection of papers all solving separate problems that are relevant to biology or biochemistry.The first paper examines problems found in self-assembling protein design. Designing polypeptides, composed of concatenated coiled coil units, to fold into polyhedra turns out to be intimately related to the concept of 1-face embeddings in graph topology. We show that 1-face embeddings can be canonicalized in linear time and present algorithms to enumerate pairwise non-isomorphic 1-face embeddings in orientable surfaces.The second and third paper examine problems found in evolutionary biology. In particular, they focus on inferring gene and species trees directly from sequence data without any a priori knowledge of the trees topology. The second paper characterize when gene trees can be inferred from estimates of orthology, paralogy and xenology relations when only partial information is available. Using this characterization an algorithm is presented that constructs a gene tree consistent with the estimates in polynomial time, if one exists. The shown algorithm is used to experimentally show that gene trees can be accurately inferred even in the case that only 20% of the relations are known. The third paper explores how to reconcile a gene tree with a species tree in a biologically feasible way, when the events of the gene tree are known. Biologically feasible reconciliations are characterized using only the topology of the gene and species tree. Using this characterization an algorithm is shown that constructs a biologically feasible reconciliation in polynomial time, if one exists.The fourth and fifth paper are concerned with with the analysis of automatically generated reaction networks. The fourth paper introduces an algorithm to predict thermodynamic properties of compounds in a chemistry. The algorithm is based on the well known group contribution methods and will automatically infer functional groups based on common structural motifs found in a set of sampled compounds. It is shown experimentally that the algorithm can be used to accurately predict a variety of molecular properties such as normal boiling point, Gibbs free energy, and the minimum free energy of RNA secondary structures. The fifth and final paper presents a framework to track atoms through reaction networks generated by a graph grammar. Using concepts found in semigroup theory, the paper defines the characteristic monoid of a reaction network. It goes on to show how natural subsystems of a reaction network organically emerge from the right Cayley graph of said monoid. The applicability of the framework is proven by applying it to the design of isotopic labeling experiments as well as to the analysis of the TCA cycle.",

author = "Nikolai N{\o}jgaard",

year = "2020",

month = apr,

language = "English",

publisher = "Syddansk Universitet. Det Naturvidenskabelige Fakultet",

address = "Denmark",

school = "SDU",

}

TY - GEN

T1 - Graph Theoretical Problems in Life Sciences

AU - Nøjgaard, Nikolai

PY - 2020/4

Y1 - 2020/4

N2 - A common task in natural sciences is to describe, characterize, and infer relations between discrete objects. A set of relations E on a set of objects V can naturally be expressed as a graph G = ¹V; Eº. It is therefore often convenient to formalize problems in natural sciences as graph theoretical problems. In this thesis we will examine a number of problems found in life sciences in particular, and show how to use graph theoretical concepts to formalize and solve the presented problems. The content of the thesis is a collection of papers all solving separate problems that are relevant to biology or biochemistry.The first paper examines problems found in self-assembling protein design. Designing polypeptides, composed of concatenated coiled coil units, to fold into polyhedra turns out to be intimately related to the concept of 1-face embeddings in graph topology. We show that 1-face embeddings can be canonicalized in linear time and present algorithms to enumerate pairwise non-isomorphic 1-face embeddings in orientable surfaces.The second and third paper examine problems found in evolutionary biology. In particular, they focus on inferring gene and species trees directly from sequence data without any a priori knowledge of the trees topology. The second paper characterize when gene trees can be inferred from estimates of orthology, paralogy and xenology relations when only partial information is available. Using this characterization an algorithm is presented that constructs a gene tree consistent with the estimates in polynomial time, if one exists. The shown algorithm is used to experimentally show that gene trees can be accurately inferred even in the case that only 20% of the relations are known. The third paper explores how to reconcile a gene tree with a species tree in a biologically feasible way, when the events of the gene tree are known. Biologically feasible reconciliations are characterized using only the topology of the gene and species tree. Using this characterization an algorithm is shown that constructs a biologically feasible reconciliation in polynomial time, if one exists.The fourth and fifth paper are concerned with with the analysis of automatically generated reaction networks. The fourth paper introduces an algorithm to predict thermodynamic properties of compounds in a chemistry. The algorithm is based on the well known group contribution methods and will automatically infer functional groups based on common structural motifs found in a set of sampled compounds. It is shown experimentally that the algorithm can be used to accurately predict a variety of molecular properties such as normal boiling point, Gibbs free energy, and the minimum free energy of RNA secondary structures. The fifth and final paper presents a framework to track atoms through reaction networks generated by a graph grammar. Using concepts found in semigroup theory, the paper defines the characteristic monoid of a reaction network. It goes on to show how natural subsystems of a reaction network organically emerge from the right Cayley graph of said monoid. The applicability of the framework is proven by applying it to the design of isotopic labeling experiments as well as to the analysis of the TCA cycle.

AB - A common task in natural sciences is to describe, characterize, and infer relations between discrete objects. A set of relations E on a set of objects V can naturally be expressed as a graph G = ¹V; Eº. It is therefore often convenient to formalize problems in natural sciences as graph theoretical problems. In this thesis we will examine a number of problems found in life sciences in particular, and show how to use graph theoretical concepts to formalize and solve the presented problems. The content of the thesis is a collection of papers all solving separate problems that are relevant to biology or biochemistry.The first paper examines problems found in self-assembling protein design. Designing polypeptides, composed of concatenated coiled coil units, to fold into polyhedra turns out to be intimately related to the concept of 1-face embeddings in graph topology. We show that 1-face embeddings can be canonicalized in linear time and present algorithms to enumerate pairwise non-isomorphic 1-face embeddings in orientable surfaces.The second and third paper examine problems found in evolutionary biology. In particular, they focus on inferring gene and species trees directly from sequence data without any a priori knowledge of the trees topology. The second paper characterize when gene trees can be inferred from estimates of orthology, paralogy and xenology relations when only partial information is available. Using this characterization an algorithm is presented that constructs a gene tree consistent with the estimates in polynomial time, if one exists. The shown algorithm is used to experimentally show that gene trees can be accurately inferred even in the case that only 20% of the relations are known. The third paper explores how to reconcile a gene tree with a species tree in a biologically feasible way, when the events of the gene tree are known. Biologically feasible reconciliations are characterized using only the topology of the gene and species tree. Using this characterization an algorithm is shown that constructs a biologically feasible reconciliation in polynomial time, if one exists.The fourth and fifth paper are concerned with with the analysis of automatically generated reaction networks. The fourth paper introduces an algorithm to predict thermodynamic properties of compounds in a chemistry. The algorithm is based on the well known group contribution methods and will automatically infer functional groups based on common structural motifs found in a set of sampled compounds. It is shown experimentally that the algorithm can be used to accurately predict a variety of molecular properties such as normal boiling point, Gibbs free energy, and the minimum free energy of RNA secondary structures. The fifth and final paper presents a framework to track atoms through reaction networks generated by a graph grammar. Using concepts found in semigroup theory, the paper defines the characteristic monoid of a reaction network. It goes on to show how natural subsystems of a reaction network organically emerge from the right Cayley graph of said monoid. The applicability of the framework is proven by applying it to the design of isotopic labeling experiments as well as to the analysis of the TCA cycle.

M3 - Ph.D. thesis

PB - Syddansk Universitet. Det Naturvidenskabelige Fakultet

ER -

Graph Theoretical Problems in Life Sciences

Abstract

Note vedr. afhandling

Fingeraftryk

Relaterede publikationer

Generic Context-Aware Group Contributions

Atom Tracking Using Cayley Graphs

Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings

Citationsformater