Please use this identifier to cite or link to this item:
doi:10.22028/D291-26594
Title: | Exact and heuristic algorithms for network alignment using graph edit distance models |
Author(s): | Ibragimov, Rashid |
Language: | English |
Year of Publication: | 2014 |
SWD key words: | Graphen Netzwerk <Graphentheorie> NP-vollständiges Problem |
Free key words: | Graph-Editierdistanz Graphalgorithmen Netzwerk-Alignment Protein-Protein-Interaktions-Netzwerk NP-Vollständigkeit graph edit distance graph algorithms network alignment protein-protein interaction networks NP-completeness graph matching |
DDC notations: | 004 Computer science, internet |
Publikation type: | Dissertation |
Abstract: | In the thesis we aim to study theoretical and practical questions of applying the graph edit distance (GED) model to the protein-protein interaction network alignment problem using topological information of graphs only. In Part II we explore some theoretical aspects of the model formulated as three different problems; Part III presents three heuristics for the PPI network alignment problem based on a GED model that counts the number of deleted and inserted edges. In dieser Arbeit werden theoretische und praktische Aspekte der Anwendung des GED(Graph Edit Distance)-Modells auf PPI (Protein-Protein-Interaktions)-Netzwerke untersucht. Hierbei werden werden ausschließlich topologische Informationen von Graphen verwendet. In zweiten Teil werden einige theoretische Eigenschaften des Modells untersucht, formuliert als drei verschiedene Problemstellungen. Im dritten Teil werden drei Heuristiken zur approximativen Lösung des PPI-Netzwerk-Alignmentproblems präsentiert, basierend auf einem GED-Modell, dass die Anzahl gelöschter und neu eingefügter Kanten auswertet. |
Link to this record: | urn:nbn:de:bsz:291-scidok-59999 hdl:20.500.11880/26650 http://dx.doi.org/10.22028/D291-26594 |
Advisor: | Baumbach, Jan |
Date of oral examination: | 5-Feb-2015 |
Date of registration: | 10-Feb-2015 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.