BioInformatics and Computational Biology II (BCBII)


Time: Tuesday, March 22nd, 14h20-16h00

Paper ID   Title
BCBII-1 Pelican – Protein-structure Alignment using Cellular Automaton models
BCBII-2 An Efficient Algorithm for De Novo Peptide Sequencing
BCBII-3 Emergent Behavior of Interacting Groups of Communicative Agents
BCBII-4 Integrating binding site predictions using meta classification
BCBII-5 Reverse engineering gene networks with artificial neural networks

Title: Pelican – Protein-structure Alignment using Cellular Automaton models
Author(s): Deepak Gangadhar
Abstract: With more than 23000 protein structures deposited in the Protein Data Bank (PDB) and more structures being discovered with each passing day, the experimental determination of the 3-dimensional structure of proteins is just the beginning of a journey in-silico. For a structural biologist, this enormous surge of structural data carries with it far greater computational challenges; Compare, align, classify, and categorize them under families, domains and functionally similar proteins already discovered. Pelican provides the structural biologist with a strong and easy technique that that will help him in facing these challenges. Pelican is a rapid way to align the backbones of two protein structures using 2-dimensional Cellular Automaton (CA) models. Breaking down the protein structure into distance matrices comprising of 5 peptide units, Pelican uses the differences of these matrices to construct the 2-dimensional CA grid. Starting from an initial unaligned state, the CA evolves through several generations according to a defined set of local rules. As the CA evolves through successive generations, the emergent patterns made by the live cells are the ones that contribute to the alignment. Pelican is also an example of a system exhibiting emergent behavior. Each cell behaves in a strictly microscopic way, but each individual cell’s behavior leads to a macroscopic long range behavior exhibited by the entire system which collectively gives the alignment.

Title: An Efficient Algorithm for De Novo Peptide Sequencing
Author(s): S. Brunetti,
D. Dutta,
S. Liberatori,
E. Mori,
D. Varrazzo
Abstract: In this paper we propose a new algorithm for the de novo peptide sequencing problem. This problem reconstructs a peptide sequence from a given tandem mass spectra data containing n peaks. We first build a directed acyclic graph G=(V, E) in O(n log n) time, where v in V such that v is a spectrum mass ion or that with complementary mass. The solutions of this problem are then given by the paths in the graph between two designated vertices. Unlike previous approaches, the proposed algorithm does not use dynamic programming, and is built in a progressive fashion using a priority queue, thus obtaining an improvement over other methods.

Title: Emergent Behavior of Interacting Groups of Communicative Agents
Author(s): Alexander Bisler
Abstract: This paper presents a simulation of the behavior of different species of birds, which share the same habitat, but manage to use different times of the day to sing their songs. Therefore, they avoid a vocal competition and improve the conditions to find a mate. Communicative agents are used to model the birds and their behavior. A simple set of rules is used to make the decisions when and how to change the time for the search for a mate. By incorporating damping and amplifying feedback loops the collective behavior of each species led the system to a solution which was favorable to all agents.

Title: Integrating binding site predictions using meta classification
Author(s): Y. Sun,
M. Robinson,
R. Adams,
P. Kaye,
N. Davey
Abstract: Currently the best algorithms for transcription factor binding site prediction are severely limited in accuracy. There is good reason to believe that predictions from these different classes of algorithms could be used in conjunction to improve the quality of predictions. In this paper, we apply single layer networks and support vector machines on predictions from 12 key algorithms. Furthermore, we use a ‘window’ of consecutive results for the input vectors in order to contextualise the neighbouring results. Moreover, we improve the classification result with the aid of under- and over- sampling techniques. We find that by integrating 12 base algorithms, support vector machines and single layer networks can give better binding site predictions.

Title: Reverse engineering gene networks with artificial neural networks
Author(s): A.Krishna ,
A.Narayanan ,
Abstract: Temporal gene expression data is of particular interest to researchers as it can be used to create regulatory gene networks. Such gene networks represent the regulatory relationships between genes over time and provide insight into how genes up- and down-regulate each other from one time-point to the next (the Biological Motherboard). Reverse engineering gene networks from temporal gene expression data is considered an important step in the study of complex biological systems. This paper introduces sensitivity analysis of trained perceptrons to reverse engineer the gene networks from temporal gene expression data. It is shown that a trained neural network, with pruning (gene silencing), can also be described as a gene network with minimal re-interpretation, where the sensitivity between nodes reflects the probability of one gene affecting another gene in time. The methodology is known as the Neural Network System Biology Approach with Gene Silencing Simulations (NNSBAGSS). The methodology was applied to artificial temporal data and rat CNS development time-course data.