Measuring the similarity of biological and medical structures through graph isomorphism

Anno
2020
Proponente Tiziana Calamoneri - Professore Ordinario
Sottosettore ERC del proponente del progetto
PE1_16
Componenti gruppo di ricerca
Componente Categoria
Ivano Salvo Componenti strutturati del gruppo di ricerca
Angelo Monti Componenti strutturati del gruppo di ricerca
Daniele Gorla Componenti strutturati del gruppo di ricerca
Adolfo Piperno Componenti strutturati del gruppo di ricerca
Componente Qualifica Struttura Categoria
FEDERICO CORO' ASSEGNISTA Dip. di Informatica - Sapienza Altro personale aggregato Sapienza o esterni, titolari di borse di studio di ricerca
MARIE-FRANCE SAGOT PROFESSORE ORDINARIO INRIA Grenoble - Francia Altro personale aggregato Sapienza o esterni, titolari di borse di studio di ricerca
BLERINA SINAIMERI PROFESSORE ASSOCIATO INRIA Grenoble - Francia Altro personale aggregato Sapienza o esterni, titolari di borse di studio di ricerca
FEDERICA GRANESE DOTTORANDA Ecole Polytechnique, Parigi - Francia Altro personale aggregato Sapienza o esterni, titolari di borse di studio di ricerca
BRENDAN D. MCKAY Professore Emerito Australian National University - Australia Altro personale aggregato Sapienza o esterni, titolari di borse di studio di ricerca
PASCAL SCHWEITZER Tenured Professor Technical University di Kaiserslautern - Germany Altro personale aggregato Sapienza o esterni, titolari di borse di studio di ricerca
Abstract

A phylogenetic tree is a rooted tree with its leaves labeled by species, or strains of species, more abstractly known as taxa and it is a model used to exhibit ancestral relations between the species. More recently, it has been observed that, when certain biological events are believed to be involved, phylogenies can be better represented as (possibly cyclic) networks.
A pathway is a series of interactions among molecules in a cell that leads to a certain product or a change in a cell and can trigger the assembly of new molecules, such as a fat or a protein.

Whichever is the structure we decide to use, there are many reasons to wonder whether they are similar or not, and hence many distances have been introduced in the literature in order to quantify the dissimilarity of two structures. Among them there are MAST and MASN, consisting in looking for the Maximum Agreement SubTree and SubNetwork, respectively, that somehow require to search isomorphic subgraphs within the input structures.

In this research, we aim at introducing for the first time a new notion of distance that works for each one of the general structures defined above; this versatility is guaranteed because it is heavily based on the concept of graph isomorphism (GI), on which the experience of the components of the research group is very strong.
Also the idea of introducing the isomorphism is completely novel and we believe we can achieve very interesting results.

ERC
PE1_16, PE6_13, PE6_6
Keywords:
BIOLOGIA COMPUTAZIONALE, ALGORITMI, FILOGENESI

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma