Detailansicht
Benchmarking edge-specific algorithms for metabolic and microbial graphs
Leopold Zehetner
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Chemie
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Biologische Chemie
Betreuer*in
Jürgen Zanghellini
DOI
10.25365/thesis.76939
URN
urn:nbn:at:at-ubw:1-11345.23213.728880-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Biologische Netzwerke stellen aufgrund ihrer inhärenten Eigenschaften von gerichteten Kanten und gewichteten Knoten und Kanten einzigartige Herausforderungen dar. Effektive Algorithmen müssen diese Komplexitäten berücksichtigen, um aussagekräftige Einblicke zu liefern. Traditionelle Algorithmen heben oft entweder Cofaktor-assoziierte Hubs hervor oder liefern inkonsistente Ergebnisse. Um diese Probleme zu adressieren, haben wir die Forman-Ricci-Krümmung (FRC) sowohl auf metabolische als auch auf mikrobielle Netzwerke angewendet und ihre Leistung mit anderen Algorithmen wie Kanten-Betweenness-Zentralität, Kanten-Pagerank, Kanten-Eigenvektor-Zentralität, Kanten-Cluster-Koeffizient, lokaler Kanten-Assortativität und Ollivier-Ricci-Krümmung (ORC) verglichen. Zusätzlich haben wir den FRC-Algorithmus durch die Normalisierung der Kantenzahl basierend auf der Knotenverbindung verbessert, um eine detailliertere und ausgewogenere Netzwerkanalyse zu ermöglichen. Wir haben die Algorithmen zunächst an kleinen und mittelgroßen zufällig generierten Netzwerken bewertet, wobei ORC eine überlegene Leistung bei der Aufrechterhaltung der gewichteten LCC nach sequentieller Kantenentfernung zeigte. Die Leistung von FRC verbesserte sich signifikant mit der Kantenzahl-Normalisierung und kam der von ORC nahe, während die Kanten-Betweenness-Zentralität am schlechtesten abschnitt. Laufzeitanalysen zeigten, dass FRC und ORC erheblich langsamer waren, was bei größeren Netzwerken nachteilig sein könnte. Bei der Anwendung dieser Algorithmen auf ein GSMM von E. coli unter glucose- und fucose-reichen Bedingungen zeigte ORC erneut die effektivste Aufrechterhaltung der LCC-Größe, gefolgt von Kanten-Pagerank und Kanten-Cluster-Koeffizient. PCA der Kantenrankings zeigte konsistente Cluster-Muster für FRC und ORC. Die Kantenzahl-Normalisierung verbesserte die Leistung von FRC, hatte jedoch begrenzte Auswirkungen auf andere Algorithmen. Wir untersuchten auch die verteilten kanten-spezifischen Werte und stellten fest, dass FRC signifikante Abweichungen zeigte, insbesondere im Fucose-Netzwerk, was auf eine reduzierte Stabilität hindeutet. Statistische Maßnahmen bestätigten, dass FRC andere Algorithmen übertraf, wenn es darum ging, zwischen glucose- und fucose-reichen Bedingungen zu unterscheiden, wenn die Verteilungen normalisiert wurden. In mikrobiellen Netzwerken von Levy et al. [1], die aus 154 Mikroben und 23.188 Interaktionen bestanden, zeigte FRC eine robuste Leistung, die durch die Kantenzahl-Normalisierung weiter verbessert wurde. FRC unterschied effektiv zwischen verschiedenen Zuständen (gesund schlank, gesund fettleibig, IBD schlank und IBD fettleibig), wobei das mikrobielle Netzwerk bei IBD fettleibigen Patienten am instabilsten war. Abschließend zeigte unsere Benchmark-Studie, dass FRC, insbesondere in Kombination mit der Kantenzahl-Normalisierung, ein leistungsfähiges Werkzeug zur Analyse von metabolischen und mikrobiellen Netzwerken ist. Es übertraf konsistent andere Algorithmen in der Aufrechterhaltung der Netzwerkintegrität und der Unterscheidung zwischen verschiedenen Netzwerkbedingungen. Zukünftige Studien sollten sich auf größere Datensätze und die weitere Validierung dieser Ergebnisse in komplexeren biologischen Netzwerken konzentrieren.
Abstract
(Englisch)
Biological networks present unique challenges due to their inherent properties of directed edges and weighted nodes and edges. Effective algorithms must consider these complexities to yield meaningful insights. Traditional algorithms often either highlight cofactor-associated hubs or produce inconsistent results. To address these issues, we applied the Forman-Ricci curvature (FRC) to both metabolic and microbial graphs and compared its performance with other algorithms such as edge betweenness centrality, edge pagerank, edge eigenvector centrality, edge cluster coefficient, edge local assortativity, and Ollivier-Ricci curvature (ORC). Additionally, we enhanced the FRC algorithm by normalizing edge numbers based on node connectivity, aiming to provide a more detailed and balanced network analysis. We first evaluated the algorithms on small and medium-sized random networks, where ORC demonstrated superior performance in maintaining the weighted largest connected compound (LCC) after sequential edge removal. FRC’s performance improved significantly with edge number normalization, closely matching ORC, while edge betweenness centrality performed the worst. Runtime analysis indicated that FRC and ORC were significantly slower, which may be a drawback for larger networks. Applying these algorithms to a genome-scale metabolic model (GSMM) of E. coli under glucose-rich and fucose-rich conditions, ORC again maintained the LCC size most effectively, followed by edge pagerank and edge cluster coefficient. Principal component analysis (PCA) of edge rankings showed consistent clustering patterns for FRC and ORC. Edge number normalization enhanced FRC’s performance, with limited impact on other algorithms. We also examined edge-specific value distributions, finding that FRC displayed significant deviations, particularly in the fucose network, indicating reduced stability. Statistical measures confirmed that FRC outperformed other algorithms in distinguishing between glucose and fucose conditions when distributions were normalized. In microbial networks from Levy et al. [1], consisting of 154 microbes and 23,188 interactions, FRC showed robust performance, further improved by edge number normalization. FRC effectively differentiated between various states (healthy lean, healthy obese, inflammatory bowel disease (IBD) lean, and IBD obese), with the microbial network in IBD obese patients being the least stable. In conclusion, our benchmarking study demonstrated that FRC, especially when augmented with edge number normalization, is a powerful tool for analyzing metabolic and microbial graphs. It consistently outperformed other algorithms in maintaining network integrity and distinguishing between different network conditions. Future studies should focus on larger datasets and further validation of these findings in more complex biological networks.
Schlagwörter
Schlagwörter
(Deutsch)
Netzwerkanalyse Forman-Ricci Curvature Metabolisches Netzwerk Mikrobielles Interaktionsnetzwerk
Schlagwörter
(Englisch)
Network analysis Forman-Ricci Curvature Metabolic Network Microbial interaction network
Autor*innen
Leopold Zehetner 
Haupttitel (Englisch)
Benchmarking edge-specific algorithms for metabolic and microbial graphs
Publikationsjahr
2024
Umfangsangabe
53 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Jürgen Zanghellini
Klassifikation
42 Biologie > 42.10 Theoretische Biologie
AC Nummer
AC17356984
Utheses ID
72282
Studienkennzahl
UA | 066 | 863 | |