Talks
Many-to-one mapping in MSA and co-graphs
Sarah Berkemer
University of Leipzig
Abstract: Just recently, a lot of work has been done in the field of co-graphs and their relations to alignments. We propose an idea in order to include many-to-one mappings of alignment characters as an expansion to (pairwise) alignment strategies which then can be used to infer the multiple sequence alignments. These mappings can be represented as graphs and hence are assumed to be co-graphs.
Ryūtō: A framework for network-flow based transcriptome reconstruction of RNA-seq data
Thomas Gatter
University of Leipzig
Abstract: In recent years, RNA-seq technology has become a staple of studies relating to the transcriptomes of organisms. Yet, exact classification remains a challenging task due to the complex nature of detectable but overlaying signals. We generalize commonly used splice graphs combined with a novel framework of new methods based on Network flows to improve predictions. However, many questions relating to these graphs remain open, highlighting the potential for further improvements.
Graph-theoretical approach for analysing brain activity
Rok Požar
University of Primorska
Abstract: The electrical activity generated by nerve cells of the brain can be measured through electrodes attached to various locations on the scalp. This technique is known as electroencephalography (EEG) and is helpful not only in clinical work, but also in studying various cognitive processes. In the talk we present how graph theory can be used to analyse EEG data. The efficiency of the graph-theoretical approach is illustrated in the case of a mild cognitive impairment.
Pentagonal clusters in fullerenes
Nino Bašić
University of Primorska
Abstract: Properties of fullerenes are critically dependent on the distribution of their 12 pentagonal faces. It is well known that there are infinitely many IPR-fullerenes. IPR-fullerenes can be described as fullerenes in which each connected cluster of pentagons has size 1.
We studied the combinations of cluster sizes that can occur in fullerenes (and whether the clusters can be at an arbitrarily large distance from each other). For each possible partition of the number 12, we are able to decide whether the partition describes the sizes of pentagon clusters in a possible fullerene.
This is joint work with Gunnar Brinkmann, Patrick W. Fowler, Tomaž Pisanski and Nico Van Cleemput.
Convex and pseudo-convex benzenoids
Tomaž Pisanski
University of Primorska
Abstract: The family of convex benzenoids has been introduced by Cruz, Gutman and Rada in 2012 [1] and was later subject of additional studies. In particular, several families of convex benzenoids that cover all cases of convex benzenoids have been identified and enumerated [2]. In this talk we present a family of pseudo-convex benzenoids that is closely related to convex benzenoids. One may say that pseudo-convex benzenoids are just tilted convex benzenoids. A similar enumeration is possible. Several existing benzenoid molecules are convex or pseudo-convex.
This is joint work with Nino Bašić.
References
[1] R. Cruz, I. Gutman and J. Rada, Convex hexagonal systems and their topological indices, MATCH Commun. Math. Comput. Chem. 68 (2012), 97–108.
[2] N. Bašić, P. W. Fowler and T. Pisanski, Stratified Enumeration of Convex Benzenoids, submitted.
Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem
Martin Milanič
University of Primorska
Abstract: Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, to appear) introduced the minimum conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has the minimum possible number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, in which the task is to minimize the number of distinct rows of the resulting matrix. Hujdurović et al. proved that both problems are NP-hard, gave a related characterization of transitively orientable graphs, and proposed a polynomial-time heuristic algorithm for the MCRS problem based on coloring cocomparability graphs.
We give new, more transparent formulations of the two problems, showing that the problems are equivalent to two optimization problems on branchings in a derived directed acyclic graph. Building on these formulations, we obtain new results on the two problems, including: (i) a strengthening of the heuristic by Hujdurović et al. via a new min-max result in digraphs generalizing Dilworth’s theorem, which may be of independent interest, (ii) APX-hardness results for both problems, (iii) approximation algorithms, and (iv) exponential-time algorithms solving the two problems to optimality faster than the naïve brute-force approach. Our work relates to several well studied notions in combinatorial optimization: chain partitions in partially ordered sets, laminar hypergraphs, and (classical and weighted) colorings of graphs.
This is joint work with Ademir Hujdurović, Edin Husić, Romeo Rizzi and Alexandru I. Tomescu.
