Computers in Scientific Discovery III - Abstracts

Keynote Talks

Visualization Software for Scientific Discovery in Toponome Research

Andreas Dress
MPI Leipzig/Shanghai

The aim of proteomics is to elucidate the complicated and highly specific relations between the distribution of proteins at any given moment in a given cell and that cell's functional state. Most existing methods rely on first homogenizing any sample under consideration, thus destroying any information regarding the actual spatial distribution of proteins within an individual cell which, however, is crucial for understanding how a cell's functional state is determined by the spatial organization of its "proteom".
In the lecture, I will present a new technology developed by Walter Schubert that allows biologists to locate up to more than one hundred distinct proteins within the same cell and, thus, to study the spatial organization of cellular protein networks, including cell-state specific colocalization and "anti-colocalization" events.
I will present samples of data generated by this technology as well as various data analysis methods that have been developed to investigate such "multi-spectral image" data and to separate signal from noise.

(Download extended abstract)

Automated Comparison of Graph Invariants

Pierre Hansen
Gerad and HEC
Montreal, Canada

A graph invariant is a function of a graph G which does not depend on labelling of G's vertices or edges. An algebraic expression of one or several graph invariants is itself an invariant. Graph theory is replete with theo- rems about graph invariants, which are either algebraic, i.e., equalities or inequalities involving such invariants, or structural, i.e., characterizations of which families of graphs are extremal for a given invariant, that is give it maximum or minimum value. Both types of results can be conjectured by the system AutoGraphiX 2 (AGX 2), in an automated way, or, in some carefully distinguished cases, in an assisted way. We report here on a systematic comparison of 20 graph invariants: for each pair of them, AGX 2 considers the four operations +,-,×,/ and derives best possible lower and upper bounding functions of the number of vertices, as well as extremal graphs. Out of 1520 cases, AGX 2 recognizes 33 known results, derives automatically algebraic and corresponding structural conjectures in 1340 cases (839 of which are proved automatically), and structural con- jectures only in 84 more cases, from which algebraic conjectures could be derived by hand in 42 cases. No results were obtained in 63 cases. Manual or assisted proofs have been obtained in 301 cases, 10 conjectures were re- futed and 274 conjectures remain open. Many examples are given. AGX 2 is also compared to the three operational systems GRAPH, GRAFFITI and HR.
(Joint work with Mustapha Aouchiche and Gilles Caporossi).

History and Progress of Structure Enumeration in Chemistry

Adalbert Kerber
University of Bayreuth

The history of molecular enumeration theory will be briefly sketched. The software package MOLGEN for the generation of connectivity isomers corresponding to a given chemical formula will be described, together with several extensions for QSAR, for molecular structure elucidation and for patents in chemistry. Afterwards, a recent extension for the generation of stereo isomers will be sketched.

Isomorphism and Automorphisms of Combinatorial Objects

Brendan D. McKay
Department of Computer Science
Australian National University

We will discuss the problem of computing the automorphism group of a combinatorial object, and the related problem of testing several objects for isomorphism. Emphasis will be strongly on the practical aspects of the problem rather than the theoretical niceties. Objects considered include various types of graphs, matrices, codes, and so forth.

The influence of the On-Line Encyclopedia of Integer Sequences on research

Neil J. A. Sloane
AT&T Shannon Labs
Florham Park, New Jersey, USA

The On-Line Encyclopedia of Integer Sequences (OEIS) is a database of over 100000 number sequences. It is freely available on the Web and is widely used. There are several ways in which it benefits research.
1. It serves as a dictionary, to tell the user what is known about a particular sequence. There are hundreds of papers which thank the OEIS for assistance in this way.
2. The associated Sequence Fans mailing list is a worldwide network which has evolved into a powerful machine for tackling new problems.
3. As a direct source of new theorems, when a sequence arises in two different contexts.
4. As a source of new research, when one sees a sequence in the OEIS that cries out to be analyzed.
The talk will be illustrated with numerous examples, emphasizing new sequences that have arrived in the past few months. Many open problems will be mentioned.

Contributed Talks -- Mathematics

On Symmetry and Topological Indices of Fullerenes

Ali Reza Ashrafi
Department of Mathematics
University of Kashan, Iran

It is well known to associate an Euclidean graph to a molecule. Balasubramanian computed the Euclidean graphs and their automorphism groups for benzene, eclipsed and staggered forms of ethane and eclipsed and staggered forms of ferrocene [see Chem. Phys. Lett. 232 (1995), 415].
In this paper, we present a simple algorithm for computing symmetry of molecules. We apply this algorithm to calculate the symmetry of some big fullerenes. The Wiener, Schultz and also Padmakar-Ivan(PI) indices of some big fullerenes are computed. Here the PI Index is a Szeged-like topological index developed very recently and defined as PI(G) = Σ[n_eu(e|G)+n_ev(e|G)], where n_eu(e|G) is the number of edges of G lying closer to u than to v, n_ev(e|G) is the number of edges of G lying closer to v than to u and summation goes over all edges of G. Finally, we pose some problems related to the symmetry and these topological indices for fullerenes.

(Download abstract)

Fullerenes and the Problems of Thomson and Tammes

Jack Graver

To each solution to the problems of Thomson (minimize the potential of n unit charged particles on the sphere) and Tammes (maximize the minimum distance between n points on the sphere - pores on a grain of pollen) we may associate the planar map given by the Dirichlet-Voronoi cells of the solution points. For small n, these maps include triangular and square faces. For n in the range 25 to 125, almost all such maps are fullerenes (only pentagonal and hexagonal faces). For n > 125, heptagonal faces begin to appear and are almost always present when n exceeds 300. However, in all large solutions the pentagonal and heptagonal faces occur in 12 distinct clusters. And each such solution has a unique underlying fullerene. Using what we know about fullerenes to build solutions to these classic problems from nature is the topic of this talk.

Conjectures on Configurations

Harald Gropp

Configurations are linear regular uniform hypergraphs. In the language of designs they are "Steiner systems where two different points may be not connected". A configuration (v_r, b_k) is a finite incidence structure of v points and b lines such that each line consists of k points, there are r lines through each point, and two different points are connected by at most one line. If v=b and r=k the configuration is called symmetric and denoted by v_k. Configurations were defined already in 1876, and the research on configurations v₄ was started in Gent (Belgium) nearly 100 years ago. In this talk the focus will be on conjectures on configurations, i.e. those which were solved in the past and those which are still open. For a given set of parameters v,r,b,k the question is: Is there a configuration (v_r, b_k) ? If yes, how many non-isomorphic are there ? Probably the possible applications of configurations as special hypergraphs in chemistry and related sciences are by far not yet exploited.

On the Steiner Quadruple Systems of Order 16

Patric Östergård

The Steiner quadruple systems of order 16 have recently been classified; there are 1,054,163 such designs. This classification - obtained in a computer search starting from the derived Steiner triple systems of order 15 - is briefly discussed. The catalogue of classified objects makes it possible to address conjectures and open questions regarding Steiner systems and related mathematical structures; a few such examples are considered.

This is joint work with Petteri Kaski and Olli Pottonen.

Representations of graphs

Tomaž Pisanski
University of Primorska and University of Ljubljana, Slovenia

A graph is a mathematical structure that is sometimes hard to separate from its visualization. An important branch of graph theory studies graph drawing problems. Recently a mathematical approach to graph visualization has been developed under the name of "graph representations". In this talk we present an outline of the theory of graph representations. A graph representation is a mapping from the set of vertices of a graph into some representation space. In general, a representation may be degenerate in various well-defined senses. Sometimes, only non-degenerate representations, or "realizations" are sought. If the representation space has the structure of metric space, it is possible to define an energy of representation. This gives rise to a number of optimization problems about graph representation which have been known in the past such as molecular mechanics, spring embedding algorithms, etc. Representations of graphs may exhibit some of the graph symmetry. Representations of graphs exhibiting specific graph symmetry are usually quite interesting to find. Finally, graphs themselves are frequently used for representing other mathematical structures, such as networks, posets, polytopes, maps, tillings, configurations, etc. This, in turn, opens up a possibility of a theory of representations for these structures. It seems that some well-known mathematical concepts such as polygons or multilaterals can be best described in terms of representations of cycles.

New Results in Constrained Circle Packings

Tibor Tarnai, Patrick Fowler

Many situations in the natural sciences and technological applications can be modelled as variants of the packing problem - the determination of efficient packings of objects in an appropriate space. In one version of the packing problem, the task is to arrange n equal circles (spherical caps) without overlap on a sphere, so that their angular radius r is a maximum. In applications it can be more useful to deal with a constrained version of this spherical circle packing problem. For example, the arrangement of packed circles may be required to exhibit a particular overall point-group symmetry; or a given number of circles form a morphological unit, and identical copies of these units should be packed on a sphere. A survey of families of multisymmetric packings, in tetrahedral, octahedral and icosahedral groups will be presented, and the polymorphism of these packings will be analysed. Additionally, three problems will be studied here: How must kN non-overlapping equal circles forming N units be packed on a sphere so that the angular diameter of the circles will be as large as possible under the constraint that, within each unit, the k circle centres lie (1) for k = 2, at the end points of a diameter; (2) for k = 3, at the vertices of an equilateral triangle inscribed in a great circle; (3) for k = 4, at the vertices of a regular tetrahedron. Computer-generated putative solutions have been calculated and will be presented for different values of N. Finally, for k = 2, the problem of packing of twin circles is investigated, where a twin is defined as two circles that are constrained to touch. Here solutions to the constrained problem are mainly expected as perfect matchings in the graphs of the solutions to the respective unconstrained problem.

Contributed Talks -- Chemistry

Supra-Faces in Nanostructures

Mircea Diudea

Tiling modification in nanostructure modeling can be achieved by sequences of classical map operations, or single generalized operations. The operations for obtaining corannulenic flowers and corannulene-like azulenic patterns were established. The first "corazulenic" tessellation is reported.
The aromaticity of some cages tessellated by the above supra-faces is discussed in terms of several criteria. The covering was given as π-electron partition within some Kekulé valence structures.
The HOMA (harmonic oscillator model of aromaticity) geometric index of aromaticity enabled the evaluation of local aromaticity of the discussed supra-faces and brought evidence for several dominant Kekulé valence structures. The most interesting is the "Kekulé-Dewar" valence structure of the cage C₁₉₂ which shows a generalized Clar, disjoint corazulenic tessellation. The original software package program CageVersatile enabled us to embed various supra-faces in surfaces of any genus.

Topology-Aided Molecular Design: The Platonic Molecules of Genera 0 to 3

Erwin Lijnen, Arnout Ceulemans
University of Leuven, Department of Chemistry
Heverlee-Leuven, Belgium

Since ancient times, scientists have been intrigued by highly symmetrical models and structures. In recent years, this has led to the successful synthesis of a multitude of molecular structures exhibiting the highest possible point group symmetries. However, as the list of point group symmetries is currently fully realized in molecules, molecular scientists must explore novel strategies. One of the possibilities is to turn to the field of topological graph theory which describes networks on surfaces with more intricate topologies than the sphere, like the torus (doughnut), double torus (pretzel), triple torus, etc. Within mathematics these networks are known as maps or embeddings and classified according to the genus (number of handles) of their underlying surface.
In the present talk we discuss a procedure to find the most symmetrical spatial realization of a given map, where we are especially interested in those maps which realize the highest possible symmetry for a given surface. They are known as 'regular maps' and can be seen as extensions of the Platonic solids as their symmetry groups act transitively on the sets of vertices, edges and faces. We also analyze the structure of the groups involved, which can viewed as 'multiples' of the classical point groups. To exemplify our procedures, we derive the highest symmetrical spatial realizations of all regular maps of genera ranging from the sphere to the triple torus.

From CID Threshold Measurements to Kinetic and Thermodynamic Information

Sanja Narancic

This project is a development of fast, reliable methods to extract kinetic and thermodynamic information from energy resolved dissociation reactions in a mass spectrometer. For the extraction of activation energies from CID threshold measurements, as well as relative thermochemistry from branching ratios in mass spectrometric dissociation reactions, one has to model energy-dependent reactive cross-section σ(E)=σ₀[1-exp(-k(E))τ] for an ion-molecule reaction in the tandem spectrometer, and therefore encounters repeatedly the need for an efficient method for the calculation of density-of-states function, ρ(E). Furthermore, the simulation is optimized using the genetic algorithm approach, providing a method, which rapidly deconvolutes measured CID thresholds.

Contributed Talks - Computing

The new developments of the AutoGraphiX system

Gilles Caporossi

The AutoGraphiX (AGX) system for computer assisted or, for some of its functions, fully automated graph theory was developed at GERAD, Montreal since 1997. We report here on the last improvements of a new version (AGX2) of that system. It contains many enhancements, as well as a new function for automated proof of simple propositions. Among other results, AGX2 led to several hundred new conjectures, ranking from easy ones, proved automatically, to others requiring longer unassisted or partially assisted proofs, to open ones. Many examples are given, illustrating AGX2's functions and the results obtained.

A Fast Exponential Algorithm for Computing the Closed-Shell Independence Number of Fullerenes

Sean Daugherty
University of Victoria, Canada

Fullerenes are all-carbon molecules in which each atom is adjacent to exactly 3 other atoms to form a cage consisting entirely of pentagons and hexagons. They can be represented by 3-regular planar graphs with face sizes 5 and 6. Chemists are interested in determining the maximum number of bromine atoms (or other bulky addends) that will bond to the surface of a fullerene. The bonding of a bromine to a carbon requires the carbon to use one electron that would otherwise be shared with neighboring carbons, effectively removing the brominated carbon from the graph. To model this disruption, we seek the maximum number of pairwise non-adjacent carbon addend sites that leave the remaining carbon atoms with a closed electron π shell. In the fullerene's representative graph, such a vertex subset is called a maximum closed-shell independent set.

We present the necessary background for constructing a fast backtracking algorithm to find the closed-shell independence number of a fullerene. We then discuss the algorithm and how the speed was achieved. Finally, we highlight the interesting computational results of an implementation run on many fullerenes.

This work is in collaboration with Wendy Myrvold and Patrick Fowler.

A Knowledge-based System for the Support of Graphtheoretical Proofs

Dieter Gernert

The interactive knowledge-based system is based upon a collection of about 1500 theorems from graph theory (conditional/unconditional equation/inequalities between graph invariants). A program run starts from a set of restrictions characterizing a class of graphs, particularly the class of all (hypothetical) counter-examples to a graphtheoretical conjecture. The system supplies advanced knowledge about the class considered, amomg other things the exact values for some graph invariants and better inclusions for most of the numerical invariants. In this way, proofs for subcases are obtained, and generally a complete proof becomes easier. The lecture is to present the principal modes of internal derivation and some examples.

Computer Algebra Experimentation in Algebraic Combinatorics

Mikhail Klin
Department of Mathematics
Ben-Gurion University of the Negev, Israel

We give a brief survey of a few lines in our investigation of coherent configurations, association schemes and related structures with the aid of computer algebra packages.
In particular, we will touch such topics as aglebraic and combinatorial automorphisms of coherent configurations, search for new strongly regular graphs, generalized quadrangles and their various axiomatic relaxations, strategies for constructive enumeration of certain color graphs.
Our presentation will be correlated with current attempts to initiate a development of computer package COCO-II, as a share package of GAP.
This presentation is based on a collaboration with M.Muzychuk, Ch.Pech, S.Reichard, A.Rosa, A.Woldar, P.-H.Zieschang and other colleagues.

Using LINK for Research on Tournaments: A User's Experience

Brenda Latka
DIMACS

This is a case study of the strengths and weaknesses of using computer software in doing research. I will talk about three related experiences using LINK to study antichains of tournaments. LINK is a system for the creation, manipulation, and drawing of graphs and hypergraphs. It was created with the intention that it could easily be used in research and education projects. A tournament is a complete directed graph. We say that a tournament S embeds in a tournament T if S is isomorphic to a subtournament of T. Tournament embedding is an order relation on the class of tournaments. An antichain of tournaments is a set of tournaments which are pairwise incomparable. First, Jon Berry, a developer of LINK, and I used LINK to study an infinite family of infinite antichains of tournaments. Second, I worked with Jon Berry as he served as an REU mentor to Chris Burrows, comparing Latka tournaments to Paley tournaments. Third, I worked with Brian Bagenstose, an undergraduate at Lafayette College, on the same infinite family of infinite antichains of tournaments.

The Evolution of GraPHedron

Hadrien Mélot

In the previous workshop (Montreal 2004), we presented for the first time a new conjecture-making system. This software, called GraPHedron, uses a polyhedral approach to find conjectures in Graph Theory. We will present the new features that have been added to GraPHedron. Among them is a procedure which derives conjectures automatically (without user intervention) in some cases. Other options have been added to help the user to extract more information about a given problem.

Phylogenetic Networks from Multi-labeled Trees

Vincent Moulton
School of Computing Sciences
University of East Anglia
Norwich, UK

It is now quite well accepted that the evolutionary past of certain species is best represented by phylogenetic networks as opposed to trees. For example, polyploids are typically thought to have resulted through hybridization and duplication, processes which are not best represented as bifuricating speciation events. Based on the knowledge of a multi-labeled tree relating collection of polyploids, we present a canonical construction of a phylogenetic network that exhibits the tree, which is in some well defined sense a minimal network having this property.

Fuigui: A Graphical User Interface for Investigating Conjectures About Fullerenes

Wendy Myrvold

Fullerenes are all-carbon molecules whose molecular structures correspond to 3-regular planar graphs that have face sizes equal to five or six. Fuigui (Fullerene Interactive Graphical User Interface) is a java program under development whose goal is to aid the exploration of fullerenes and their parameters. Some of the design challenges covered in this talk are:

1. Making the system fully interactive, fast and fun to play with.
2. Plug and play parameters- a user can add his or her own fullerene parameters without changing the code for fuigui.
3. Drawing pictures which are pleasing to the chemists.
4. Facilitating animated algorithms.

A demonstration will be given of the current state of the system. The talk will conclude with ideas for future enhancements.
This is joint work with Bette Bultena, Sean Daugherty, Patrick Fowler, Sameer Girn, Marsha Minchenko, and Jennifer Woodcock.

Grinvin: The Graph Investigation Framework

Adriaan Peeters
Applied Mathematics and Computer Science
Ghent University

The Graph Invariant Investigator (GrInvIn) is a software framework which provides support for generating, drawing and investigating graphs and their properties. One way to investigate these properties is by deriving conjectures on (sets of) graphs.

The GrInvIn framework has been designed to be open, with extendability as the main goal, thus allowing the integration of existing and/or external tools through simple plug-ins. A researcher can for example easily add a conjecturing engine, a graph invariant computing routine or an algorithm to compute a useful embedding for a graph. A lot of effort has been put in the software design of the framework.

In this talk we will explain the decisions we had to make and the difficulties which arose in the design of GrInvIn. We will also show how different kinds of plug-in can be created and used in the framework.

Contributed Talks - Bioinformatics

Clustering the Protein Databank

Eric Breimer*

Bioinformatics applications have significantly changed the nature and scope of the graph clustering and graph partitioning problem. Predicting the structure of proteins is one such application where data clustering is an important step in understanding the relationships between the sequence of amino acids and the structure of a protein. The Protein Databank (www.rcsb.org) forms a graph with over 33,400 vertices and over 500 million edges, where each vertex is a protein and the value of each edge represents the structural similarity between two proteins. The clusters that arise from structurally similar proteins may significantly overlap. Conventional clustering or graph partitioning algorithms are not suited for this type of problem.
This talk will describe the characteristics of graphs that arise from protein similarity, techniques for handling very large, complete graphs, and algorithms for discovering locally optimal, dense sub-graphs. If time permits, I will also address how the emergence of bioinformatics has changed my approach in teaching traditional undergraduate courses such as Analysis of Algorithm and Discrete Math.

*Contributions by Darren Lim, Mark Goldberg, Malik Magdon-Ismail and Jeff Baumes.

Graphs, Permutations and Sets in Genome Rearrangement

Anthony Labarre

Genome rearrangement is the field in bioinformatics that studies and models how a collection of genomes evolve and is generally expressed in the following way: given two (or more) genomes, find a shortest sequence of mutations that transform one into the other. Several models have been proposed, that differ either by the kind(s) of mutations taken into account or by the way genomes are represented, depending on the different biological assumptions that can be made. We review some of these models and known results, explain how computers have already helped in this area and suggest some further possible uses for them.

Posters - Chemistry

Q-Conjugacy Character Tables of Some Chemical Molecules, An Application of Combinatorial enumeration of isomers

Ghorban Ali Moghani¹ and A.R.Mirhabibi²
1. Department of Nano-Materials, Iran Color Research Center (ICRC), Tehran, Iran
2. Inorganic Pigments & Ceramic Coating Department, Iran Color Research Center (ICRC), Tehran, Iran

It is necessary to generate the automorphism group of a chemical graph in computer-aided structure elucidation. An Euclidean graph associated with a molecule is defined by a weighted graph with adjacency matrix M = [d_ij], where for i≠j, d_ij is the Euclidean distance between the nuclei i and j. In this matrix d_ii can be taken as zero if all the nuclei are equivalent. Otherwise, one may introduce different weights for distinct nuclei.
Combinatorial enumerations by means of Unit Subduced Cycle Indices (USCIs) is discussed by using the point groups as examples. Several properties of USCIs are discussed by clarifying the relationship between double cosets and the subduction of the USCIs. This treatment provides us an alternative formulation of the USCIs. In this paper we present some MATLAB and GAP programs to find the automorphism group as well as compute Markaracter Table and Q-Conjugacy Character Table for some Chemical Molecules such as fullerenes, Naphthalene, Antheracene , Nano Cluster point groups.
For example, Symmetry Group of Naphthalene and Antheracene is Z₂×Z₂, Symmetry Groups for Clusters of Ag and Cu are id, Z₂, S₃, S₄, D₈, D₁₀, Z₂×D₈, D₂₀ which we use them to find their Q-Conjugacy Character Tables and enumeration of their isomers.

Posters - Education

Visualizing Cauchy's Interlacing Property for Line Distance Matrices

Gašper Jaklič and Tomaž Pisanski
University of Ljubljana

Download abstract

Graph Theory Education with newGRAPH

Dragan Stevanović

Following global eLearning trend, we witness attempts to introduce computers in every pore of the process of learning. In the field of algorithmic graph theory, a predominant option is visualization of algorithms. However, in the theory itself, there are not many eLearning approaches. A particularly interesting example is the use of Graffiti, where students construct (counter)examples of graphs for a set of automatically generated conjectures, and at the end of the process attempt to prove the conjectures by hand. In this poster, we will show how system newGRAPH may serve in a more traditional way to provide interactive examples which can help students better understand graph theory concepts. Further, simple exercises, such as "find a 3-regular graph without a perfect matching", may be automated so that the student is informed of its success throughout solving process.

Posters - Bioinformatics

Can Multiscale Modelling Explain the Un-natural Interactions of HIV-1 TAR-RNA with Human Transcription factors?

Mahmud Tareq Hassan Khan^1,3, Olayiwola Adekoya¹, A.B.S.M. Osman Gani¹, Carlo Mischiati³, Arjumand Ather³, Monica Borgatti³, Ingebrigt Sylte¹ and Roberto Gambari^2,3
1Department of Pharmacology, Institute of Medical Biology, University of Tromsø, 9037 Tromsø, Norway; ²Biotechnology Center, University of Ferrara, Italy; ³ER-GenTech, Department of Biochemistry and Molecular Biology, University of Ferrara, Italy.

The interplay between the life cycle of the Human Immunodeficiency Virus type 1 (HIV-1) and biological parameters of infected cells is pivotal for the understanding how the HIV-1 gene expression is controlled and for the design and development of anti-HIV-1 drugs exhibiting high levels of specificity. An example of the interplay between HIV-1 gene expression pathways and the cellular genome is the recruitment of cellular transcription factors to the HIV-1 LTR. This is demonstrated to play a very important role in transcriptional regulation of the HIV-1 cell cycle. On the other hand, the HIV-1 genome, in addition to structural genes, encodes a set of regulatory proteins that modulate viral gene expression in infected cells. Among them, Tat is required to induce high level of expression of the HIV-1 genome after binding to a structured TAR RNA. The TAR-RNA sequences have been objects of several investigations. TAR RNA is encoded by nucleotides spanning the region extending from +1 to + 57 and folds into a stem-loop structure composed of two domains: a three-nucleotide bulge and the loop sequence. Few informations are reported in the literature on the possible interactions between cellular proteins and the HIV-1 TAR RNA, despite the fact that it is well established that nuclear proteins binding the HIV-1 TAR RNA are present in HIV-1 infected cells and might retain regulatory roles. In this respect we performed several in silico screening of the possible interactions between the HIV-1 TAR RNA and human transcription factors which we tried to prove later in molecular biological approaches. In this account we are reporting the un-natural interaction between the TAR RNA with nuclear factor kappa beta (NFkB). Our first approach was to study the interaction using the docking simulation of TAR and NFkB using suitable macromolecular docking algorithm. Secondly the results we compared with with electrophoretic mobility shift assays (EMSA) and surface plasmon resonance (SPR) based biospecific interaction analysis (BIA) using an optical biosensor. And finally, the modelled RNA-NFkB complex simulated at different temperatures with AMBER biomolecular simulation program at 3 ns on HPC superdome using parallel processors.

Posters - Computing

Distributed fault detection: model-based versus AI approaches

Rene Boel
Ghent University

The analysis of large systems requires distributed algorithms and implementations, in order to limit the computational complexity, in order to improve the robustness of the analysis against failures in the communication channels, and in order to reduce the dependency of the analysis results on mismatches between plant and model (a hard problem for large systems, due to the frequent system updates).
My research work has recently been concentrated on model-based fault detection and state estimation for such large plants. In the context of fault detection for backup protection of power systems, compositional models consisting of many interacitng Petri nets were used. In the context of road traffic state estimation particle filtering (simulation based) approaches were used for networks consisting of many interacting roads.
One important question to be answered for these distributed algorithms, implemented via communicating local agents, is: what is the minimal set of messages to be exchanged between different agents in order to achieve acceptable performance? An interesting question in the context of the "Discovery" conference is whether this information exchange depends strongly on the a priori knowledge of a model?

• How much extra information must be transmitted if local agents do not know a model of their interaction a priori?
• Can they discover their local model by using local information only, or do they need co-operation from other agents in order to discover their local model?
• How can local agents discover the structure of the global network? Is this necessary?

Search Algorithms for Maximal Partial Ovoids and Minimal Blocking Sets in Generalized Quadrangles

Miroslava Cimráková
Ghent University

Some standard problems in finite geometry are

• determination of the maximal and minimal number of points of a substructure satisfying specific geometric conditions,
• exploration of the spectrum of sizes for which such substructures exist,
• classification of substructures of a given size.

In this research we focus on maximal partial ovoids and minimal blocking sets in classical generalized quadrangles. The search for these substructures can be translated to algorithmic problems, such as the maximum clique problem, which are NP-hard.
Using standard backtracking strategies, together with pruning techniques based on problem specific properties, we obtain non-trivial results which are mathematically interesting. For small parameters we get exact answers concerning the size of the largest/smallest substructures or the complete classification of all substructures of a given size. Some of the results improve earlier theoretical bounds. Also heuristic techniques lead to new results, especially when exploring the spectrum of sizes for problems with larger parameters.

Covering nanostructures by map operations: CageVersatile Software

Mircea Diudea

CageVersatile(Net) CVNET software package,written in C, is a program, written on the ground of map operations as a theoretical support, for generating coordinates of closed or open lattices covering nanostructures. It includes the main map operations: dual, medial, truncation, leapfrog, chamfering, capra, as well as some generalized operations.
The program works either on single or multiple files of input. As input, the hin files of HyperChem is used. The output files represent transformed maps, written as hin files in a Rez directory, automatically created within the input directory. The program also provides a text file with the number of size of polyhedral faces of the map.

Generation of Association Schemes

Jan Degraer
Ghent University

Download abstract

Mining Tree Queries in a Graph

Bart Goethals, Eveline Hoekx and Jan Van den Bussche
Universiteit Hasselt

We present an algorithm for mining tree-shaped patterns in a large graph. Novel about our class of patterns is that they can contain constants, and can contain existential nodes which are not counted when determining the number of occurrences of the pattern in the graph. Our algorithm has a number of provable optimality properties, which are based on the theory of conjunctive database queries. We propose a database-oriented implementation in SQL, and report upon some initial experimental results obtained with our implementation on graph data about food webs, about protein interactions, and about citation analysis.

Posters - Mathematics

Permutations Arrays and Isometries of Sym(n)

Mathieu Bogaerts

Let Sym(n) be the group of all permutations of n elements. If p₁, p₂ are two permutations such that p₁ and p₂ coincide in λ positions, the Hamming distance between p₁ and p₂ is the integer d_n(p₁,p₂) = n - λ.
A permutation array (PA) Γ_(n,d) of size s and minimum distance d is a set of s permutations of n elements such that the distance between any two permutations is at least d. Permutation arrays have applications in code theory, taking as codewords the permutations of a given PA.
Let Iso(Sym(n)) be the group of isometries of the metric space (Sym(n), d_n). Our goal is to construct permutation arrays and classify them up to isometry. Our algorithms use interesting links between combinatorics and graph theory.

Numbers of Faces in Disordered Patches

Claudia Justus, Gunnar Brinkmann, Jack Graver

It has been shown that the boundary structure of patches with all faces of the same size k, all interior vertices of the same degree m and all boundary vertices of degree at most m determines the number of faces of the patch. In case of at least two defective faces, that is faces with degree k'≠k, it is well known that this is not the case. Patches with a limited amount of disorder are especially interesting for the case k=6, m=3 and k'=5, which corresponds to polycyclic hydrocarbons with a limited number of pentagons and to subgraphs of fullerenes. The last open question was the case of exactly one defective face or vertex. We generalize the known results and allow vertices of degree larger than m on the boundary, sequences of degrees on the boundary to be identical only modulo m, and vertex and face degrees in the interior that are multiples of m resp. k. Furthermore we prove that in case of at most one defective face with a degree that is not a multiple of k the number of faces of a patch is determined by the boundary. This result implies that fullerenes cannot grow by replacing patches of a restricted size.

Simplicial chains and the tetrahelix

Jean-Luc Michel

A tetrahedral chain is a sequence of regular tetrahedra in R³ such that any two consecutive tetrahedra have one facet in common.

By placing at the vertices of each tetrahedron of the chain a sphere whose radius is half the edge length of the tetrahedra, we obtain a sphere packing. Thus it is not so surprising that such tetrahedral chains appear in the study of some molecular structures.

A tetrahedral chain is closed if the first tetrahedron has a facet in common with the last one. Does there exist a closed tetrahedral chain? We generalize this question to simplicial chains in any Euclidean space Rⁿ, i.e. to sequences of regular simplices of Rⁿ such that any two consecutive simplices have one facet in common. A regular simplex of Rⁿ is the convex hull of n+1 points of Rⁿ such that the distance between two of these points does not depend on the choice of the two points.

We prove that closed simplicial chains do not exist in Euclidean spaces of dimension at least 3.

We also prove that the symmetry group of the tetrahelix (an infinite tetrahedral chain), also known as the Boerdijk-Coxeter helix, does not contain any translation. This group is generated by a twist whose angle θ satisfies the equation cos θ=-(2/3), so that θ/π is an irrationnal number.

Construction Techniques for Incidence Structures

Joost Winne
Ghent University

Download abstract

Round Tables

Conjecturing round table

Gilles Caporossi

Conjectures play a predominant role in mathematics (and therefore graph theory). Almost all theorems have been conjectures, at least in the mind of their authors. Computer programs actually may be used to find conjectures in a more or less automated way however the task of finding conjectures is not as easy as it could appear. In order to be interesting, a conjecture must not be trivial, one should expect it to be true and find it useful.
In this round table, various aspects of computer aided conjecture generation will be discussed such as the level of automation and the nature of the conjectures (most of the theorems in graph theory could not be produced as conjecture by any actual computer program) among others.
One goal of this round table is to bring together people working on computer programs and graph theorists in order to evaluate the developments to be achieved in computer aided conjecture generation. Indeed, depending on the participants, other fields related to conjectures may be discussed.

Computer science: Aligning efforts in software development

Kris Coolsaet

A lot of software which could be useful to all of us is being developed all the time. However, loads of programs remain unknown to the community (and hence unused). Worse even, many algorithms are implemented time and time again, going through the same tedious cycles of development, coding and debugging. We can easily think of many reasons why this is so:

• Often a program is written overnight by a lone developer who only needs to use it once and does not realise that also other users might be interested.
• Sometimes the effort to rewrite the software in such a way that it works in a more general setting just takes too much effort.
• Maybe an application was written in Fortran years ago and uses a file format which is not well documented.
• etc.

As chairman of the round table session on 'aligning efforts in software development' I would like to invite you to discuss (solutions to) this problem in the specific context of graph algorithm software. Personally I would like to put forward the following view: programming and algorithm development is not the same as software development. Mathematicians and 'theoretical' computer scientists are in general very good programmers and even better algorithm developers, but we need more true software engineers. Sufficient attention to 'pluggability', 'reusability' and 'maintainability' might bring us a long way towards providing a framework in which casual programmers can concentrate on their algorithms without needing to worry about the intricacies of user interface programming, database connectivity, file formats, etc...

Teaching Mathematics

Ermelinda Delavina

The use of computer software for teaching mathematics seems an expanding endeavor, and improvements of software packages may further encourage teachers to utilize software in their teaching. As chairperson of this round table discussion, I invite participants to give examples of current use of software for teaching graph theory in the classroom (or other subfields of mathematics) or for enrichment experiences at the undergraduate and graduate level. In an effort to give the discussion some direction and purpose, I would like to encourage our discussion of this topic to address educational objectives for a learner and for a teacher, and to address potential indicators of meeting those objectives. At least one participant has expressed interest in discussing the use of software for graph theory in high school and I look forward to any other suggestions.

Discovery in Bioinformatics

Susan L Epstein

The roundtable on Discovery in Bioinformatics will address the existence and applications of motifs, that is, invariant biological patterns, including but not limited to subgraphs, residue strings, and tertiary structures. Of particular interest will be demonstrations that such motifs exist, algorithms to detect them, and proposals for their appropriate application.

Chemistry round table

Reinhard Laue

What is the role of universities in the development of software for Chemistry?

Some observations may stimulate the discussion:

• Commercial software needs support and development in a fast changing world of systems.
• Research is funded only for a few years, mostly young researchers. University software cannot be maintained over a long time.
• How can we integrate our work into a long time project?
• Results are free in the academic world.
• Industry, especially in Chemistry, hides the results. Data are proprietary. Cooperation is based on keeping research results secret.
• Does it make sense to work on open source alternatives?
• What are the topics we should focus on to meet such constraints? What should be left to industry?
  • Models for representing molecules, general or specialized
  • Graph theoretic indices
  • Spacial modellings
  • Mathematical prediction with prescribed properties
  • Automatic structure elucidation based on spectra
  • Databases of structure property relationships
  • Build prototypes only or perfect modules for well defined tasks

It is hoped that an exchange of experience and ideas helps to find individual answers or even to find a common strategy. But maybe planning does not make any sense?

Mathematics round table: Graph theoretical methods in carbon chemistry (benzenoids, fullerenes, etc.)

Patrick Fowler and Horst Sachs

The mathematics round table will be about interaction between mathematics and chemistry, and will concentrate on graph theory as used in chemistry: conjectures, techniques, utility or otherwise of invariants, interesting classes of graphs, software, open questions ... and other topics as raised by the participants.