# 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.