Simona Bonvicini: A graph theory problem related to the self-assembly of DNA structures

Predavateljica: Simona Bonvicini, Università di Modena e Reggio Emilia, Italija

Simona Bonvicini je prejemnica nagrade Petre Šparl za leto 2020. Nagrado je podelila revija Ars Mathematica Contemporanea za najboljši članek mlade matematičarke, objavljen v zadnjih petih letih. Več o nagradi na https://amc-journal.eu/index.php/amc/article/view/2321/1488.

Naslov predavanja: A graph theory problem related to the self-assembly of DNA structures

Povzetek. The self-assembly of DNA structures can be obtained by several methods that are based on the Watson-Crick complementary properties of DNA strands. We consider the method of branched junction molecules: star shaped molecules whose arms have cohesive ends that allow the molecules to join together in a prescribed way and form a larger molecule (DNA complex).

In graph theory terminology, a branched junction molecule is called a tile and consists of a vertex with labeled half-edges; labels are the cohesive ends and belong to a finite set of symbols, say {a, aˆ : a ∈ Σ}. A tile is denoted by the multiset consisting of the labels of the half-edges (the tile type). We can create an edge between two vertices u, v if and only if u has a half-edge labeled by a and v has a half-edge labeled by aˆ; the edge thus obtained is said to be a bond-edge of type aaˆ. By connecting the vertices according to the labels, we can construct a graph G representing a DNA complex.

The following problem is considered: determine the minimum number of tile types and bond-edge types that are necessary to construct a given graph G.

In this seminar we discuss the above problem and show some techniques providing an upper bound for the number of bond-edge types that are necessary to construct an arbitrary graph.

Based on a joint work with Margherita Maria Ferrari.