Talks
Rule-Based Gillespie Simulation of Chemical Systems
Jakob Lykke Andersen
University of Southern Denmark in Odense
Abstract: We implement a modular stochastic simulation engine for a rule-based chemical models where atoms are explicitly represented. Using a strategy framework originally developed for generating reaction networks, it is possible to tune the degree of network-freeness of the simulation.
Convexity Deficit of Benzenoids
Nino Bašić
University of Primorska & IMFM
Abstract: In 2012, a family of benzenoids was introduced by Cruz, Gutman and Rada, which they called convex benzenoids. We introduce a new topological index for benzenoids, called convexity deficit. It measures by how much a given benzenoid departs from convexity. It is computed from the boundary-edges code. Convex benzenoids, in particular, are exactly the benzenoids having convexity deficit equal to 0. We also introduce a family of quasi-convex benzenoids (i.e. the family of non-convex benzenoids that are closest to convex) and a subfamily of quasi-convex benzenoids that we call pseudo-convex. We investigate some of their properties and concentrate especially on those benzenoids that are extremal with respect to convexity deficit.
Network Statistics
Andre Fujita
University of São Paulo
Abstract: Graphs have been used as tools to study the interaction among components of a system in several domains, such as Physics, Biology, Engineering, and Social Sciences. Traditional graph theory assumes that the graph is deterministic, and the developed algorithms aim at identifying patterns (motifs), colors, and isomorphism. More recent approaches to analyze empirical graphs are based on measures that characterize complex networks, such as centrality and clustering coefficients. However, empirical networks present two often ignored characteristics, i.e., heterogeneity and randomness, which make the use of them very limited. Notice that even complex network measures do not explain the involved mechanisms due to the lack of a mathematical model that generates a graph with a given set of characteristics (e.g. centrality measure). Thus, a natural solution for this problem could be the use of formal statistical methods on random graphs, such as methods for parameter estimation, model selection, comparison, correlation, and causality. In this talk, I will present the main advances in network statistics and some tools to analyze empirical graphs.
Computing the Wiener Index of a Tree from Its Terminal Matrix
Tomaž Pisanski
University of Primorska & IMFM
Abstract: In this talk we present an algorithm for computing the Wiener index of a tree from the distance matrix of its leaves, known also as the terminal matrix of a tree. The algorithm performs better than the linear time algorithm for trees that have a large number of vertices of valence 2.
This is work in progress with Andrei Dobrynin and Bojan Mohar.
From Best Matches to Gene Families: How to Use Paralogs in Phylogenomics
Peter F. Stadler
Leipzig University
Abstract: Best match graphs (BMGs) arise naturally as the first processing intermediate in algorithms for orthology detection. Let T be a phylogenetic (gene) tree and σ an assignment of leaves of T to species. The best match graph (G, σ) is a digraph that contains an arc from x to y if the genes x and y reside in different species and y is one of possibly many (evolutionary) closest relatives of x compared to all other genes contained in the species σ(y). I will give two alternative characterizations of BMGs and show that a minimally resolved tree that explains a BMG can be reconstructed in cubic time. The symmetric part of a BMGs represents the empirical estimate for the orthology relation on the gene set as inferred from a reciprocal best match heuristic. BMGs are therefore close relatives of co-graphs, which describe perfect duplication/speciation scenarios. Whenever a BMG deviates from a cograph structure, this implies that the reciprocal best match heuristic has produced incorrect orthology assignments. A reasonable approach therefore it to correct the data by editing the BMG into its nearest co-graph. Cographs, in turn, are equivalent to event-labeled gene trees that identify duplication and speciation events. These trees also impose constraints on the species tree and the possible reconciliation maps. Taken together, therefore, it is possible to start from reciprocal best matches of the proteomes of a set of species and eventually arrive at the phylogenetic tree of these taxa without the use of a conventional tree reconstruction method. In fact, an analysis of the workflow show that it only makes use of gene duplication events, while sets of 1-1 orthologs do not contribute at all. In this sense the approach is orthogonal to classical phylogenetic methods.
