A first step towards determining biological traits from phenotypespaces: The strong product of di-graphs

Marc Hellmuth
University of Greifswald

Peter F. Stadler
University of Leipzig

Tilen Marc
University of Ljubljana


Minisymposium: GRAPH PRODUCTS

Content: Product graphs and product-like structures play a central role in theoretical biology. To determine traits that can vary independently through evolution one can equivalently ask for the (local) prime factors of the underlying phenotypespace. The topology of the phenotypespace corresponds (at least locally) to the direct product of di-graphs. Hence, of immediate interest for biologists are algorithms that determine or approximate the prime factors of the phenotypespace w.r.t.\ the direct product. Here we consider a special case of the direct product of di-graphs, namely the strong product, and show that the respective prime factors can be determined in polynomial time. The factorization algorithm depends on the construction of the Cartesian skeleton, which we introduce here for di-graphs as a generalization of the well-known Cartesian skeleton of undirected graphs. Finally, we discuss open problems and challenges that we are dealing with when we want to find approximate factors of a ``real-world'' phenotypespace.

Back to all abstracts