Talk Abstract

Systems Biology Series

10/27: Hamid Bolouri, Professor

Algorithm Talk: Four computational tools for reconstruction and analysis of genetic regulatory networks I will describe a suite of tools developed by my former group at the Institute for Systems Biology (see http://MAGNET.systemsbiology.net). Together, these tools permit statistical data integration/filtering (Pointillist), Transcription factor binding site prediction (Mogul), network reconstruction and visualization (BioTapestry) and network dynamical modeling and analysis (Dizzy). I will outline the techniques and methodology underlying each tool and show examples of their application to biology.

General Talk: Understanding the dynamic behavior of large scale genetic regulatory networks by functional decomposition A number of mechanistic and predictive genetic regulatory networks (GRNs) comprising dozens of genes have already been characterized at the level of cis-regulatory interactions. Reconstructions of networks of 100's to 1000's of genes and their interactions are currently underway. Understanding the organizational and functional principles underlying these networks is probably the single greatest challenge facing genomics today. I will review the current approaches to deciphering large-scale GRNs and discuss some of their limitations. I propose a bottom up approach in which large-scale GRNs are first organized in terms of functionally distinct GRN building blocks of one or a few genes. Biological processes may then be viewed as the outcome of functional interactions among these simple, well-characterized functional building blocks. I will describe several putative GRN functional building blocks and show that they can be located within GRNs on the basis of their interaction topology and additional, simple and experimentally testable constraints.

Computational Biology Series

11/10: Tatsuya Akutsu, Professor

Topic: Approximating Tree Edit Distance Using Euler Strings and Modified Euler Strings Comparison of tree structures is important in several diverse areas such as computational biology, XML databases and image analysis. Though various measures have been proposed for computing the similarity between trees, the edit distance between rooted and ordered trees is well-studied and widely-used. For this tree edit distance problem, Tai first developed a polynomial time algorithm, from which several improvements followed. Among these, a recent algorithm by Damaine et al. is the fastest in the worst case and works in O(n^3) time where n is the maximum size of input trees. They also proved an Omega(n^3) lower bound for the class of decomposition strategy algorithms. In this talk, we propose approximation algorithms for the tree edit distance problem using Euler strings and modified Euler strings. We show that the unit cost tree edit distance is at least half and at most 2h+1 of the edit distance for the Euler strings, where h is the minimum height of two trees. This result gives a good approximation ratio if the heights of input trees are low. However, it does not guarantee any upper bounds of tree edit distances if the heights of input trees are O(n). Therefore, we further improve this result by modifying the Euler string. We show that the unit cost edit distance between trees is at least 1/6 and at most O(n^(3/4)) of the unit cost edit distance between the modified Euler strings, where we assume that the maximum degree of trees is bounded by a constant. This result leads to the first O(n^3) time algorithm for computing the tree edit distance with a guaranteed approximation ratio (for bounded degree trees).

12/7: Tao Jiang, Professor

Topic: A Parsimony Approach to Genome-Wide Ortholog Assignment The assignment of orthologous genes between a pair of genomes is a fundamental and challenging problem in comparative genomics. Existing methods that assign orthologs based on the similarity between DNA or protein sequences may make erroneous assignments when sequence similarity does not clearly delineate the evolutionary relationship among genes of the same families. In this paper, we present a new approach to ortholog assignment that takes into account both sequence similarity and evolutionary events at genome level, where orthologous genes are assumed to correspond to each other in the most parsimonious evolving scenario under genome rearrangement and gene duplication. It is then formulated as a problem of computing the signed reversal distance with duplicates between two genomes of interest, for which an efficient heuristic algorithm was given by introducing two new optimization problems, minimum common partition and maximum cycle decomposition. Following this approach, we have implemented a high-throughput system for assigning orthologs on a genome scale, called MSOAR, and tested it on both simulated data and real genome sequence data. Our predicted orthologs between the human and mouse genomes are strongly supported by ortholog and protein function information in authorative databases, and predictions made by other key ortholog assignment methods such as Ensembl, Homologene, INPARANOID, and HGNC. The simulation results demonstrate that MSOAR in general performs better than the iterated exemplar algorithm of David Sankoff's in terms of identifying true exemplar genes.