Algorithms and Computational Methods for Biochemical and Evolutionary Networks
December 15-18, 2004     Recife, BRAZIL


The following invited speakers have confirmed presence at CompBioNets 2004.



Speaker: Amihood Amir

Title: Two Glass Balls and a Tower

Abstract: The bounded divide-and-conquer technique has been pioneered in Pattern Matching by Abrahamson. Since its inception, the technique has proven useful in numerous results in combinatorial pattern matching and computational biology. Its wide use warrants a deeper study.

We will review and abstract the idea and show how it has aided in efficiently computing Hamming distance, less-than matching, masked maximum, and a new result - approximate weighted sequences matching.


Speaker: Mathieu Blanchette

Title: What the mammalian zoo tells us about our genome and the genome of our ancestors

Abstract: New complete mammalian genomes are now being sequenced each year. In this talk, I will describe a few things that can be learned from this wealth of comparative genomics data. I will first describe computational methods for the detection and the characterization of non-coding functional regions of the human genome based on comparative genomics. A 1.87 Mb region surrounding the CFTR gene and for which orthologous sequences are available in a large number of mammals will be used as an example. In the second half of my talk, I will describe how, given the genomic sequences of several mammals, it is possible to reconstruct surprisingly accurately the genomic sequence of certain early mammalian ancestors sequences. I will describe the algorithms required to achieve this, and the set simulations suggesting that such a reconstruction could probably be done with a 98% base-by-base accuracy, in most regions of the genome. Such an ancestral reconstruction, though imperfect, will help understanding mammalian evolution and primate and human-specific innovations. It will also help the functional annotation of our genome.


Speaker: Vincent Moulton

Title: Phylogenetic networks: How to build them and what to do with them

Abstract: Phylogenetic networks are a generalization of phylogenetic trees that permit the representation of conflicting signal or alternative
phylogenetic histories. Networks can provide a useful tool
for phylogenetic analysis when the underlying evolutionary history
is non treelike. For example, recombination, hybridization, and
lateral gene transfer can all lead to histories that are not adequately
modeled by a single tree. Moreover, even in case the underlying history is
treelike, phenomena such as parallel evolution and sampling error
can make it difficult to represent the history by a single
tree. In such situations networks can be a useful way for
representing ambiguity or for simultaneously visualizing a collection of
feasible trees. In this talk we will present a brief overview of
phylogenetic networks, and some new methods for their construction.
We will also discuss how to interpret such networks, which will
naturally lead us to some directions for future research.


Speaker: Gene Myers

Title: Whole Genome Sequencing, Comparative Genomics, and Systems Biology

Abstract: The whole-genome shotgun sequencing method with paired end-reads has proven rapid and economical, producing high-quality reconstructions of Drosophila (2000), Human (2001) and Mouse (2001), in quick succession. We discuss the overall algorithmic strategy, and the results one can expect by comparing the whole genome assembly of Drosophila against the recently finished sequence, and advances such as high-density, solid state sequencing and single molecule detection systems.

We anticipate having the euchromatic portions of the genomes of twelve species of Drosophila in the next year. We discuss the current state of the art in comparative gene finding, cis-control module finding, and possible improvements. The hope of these approaches is that we will be able to accurately identify the "parts lists" of the D. melanogaster genome, a basic prerequisite for systems biology.

We conclude with a segment on the possibility of a program of high-throughput in-situ image analysis in Drosophila embryos. We describe what information we might collect and what we might be able to infer from it. 

It is our contention that this may be the best way to understand development from a systems perspective.



Speaker: Ron Pinter

Title: Integrative Analyses of Interaction Networks Underlying the Cellular
Circuitry in Yeast

Abstract: Cellular processes are regulated by interactions between various types of molecules, such as proteins, genes, and metabolites. Among these, the interactions between proteins and the interactions between transcription factors and their target genes play a prominent role, controlling the activity of proteins and the expression levels of genes. A significant number of such interactions has been revealed recently via high throughput
technologies. These data can be represented as a network of interactions
describing the circuitry responsible for the regulation of a variety of
cellular processes. Analysis of this cellular circuitry is one of the major
research goals in the post genomic era.

Previous studies have analyzed aspects of this network concentrating on
either transcription-regulation or protein-protein interactions separately.
Here we search for composite network motifs: characteristic network patterns consisting of both transcription-regulation and protein-protein interactions that recur significantly more often than in random networks. To this end we developed algorithms for detecting motifs in networks with two or more types of interactions and applied them to an integrated data set of
protein-protein interactions and transcription regulation in Saccharomyces
cerevisiae. We found a two-protein mixed-feedback loop motif, five types of
three-protein motifs exhibiting coregulation and complex formation, and many motifs involving four proteins. Virtually all four-protein motifs consisted
of combinations of smaller motifs. This study presents a basic framework
for detecting the building blocks of networks with multiple types of

Joint work with Esti Yeger-Lotem, Samuel Sattath, Nadav Kashtan, Shalev
Itzkovitz, Ron Milo, Uri Alon, and Hanah Margalit.



Speaker: Eduardo Rocha

Title: Order and disorder in bacterial genomes

Abstract: The availability of more than 200 bacterial genomes allows the
comparative analysis of genome structure and composition in relation to
bacterial lifestyle and evolution. Replication plays a major role among
the elements organizing Bacterial genomes. The replication asymmetries
induce biases at the levels of nucleotide composition and gene
distribution that strongly fashion the chromosome. As a consequence the
chromosome seems more structured than previously thought. However,
Bacterial genomes also contain a very significant number of repeats
that may generate genetic variability and shuffle the chromosome. Such
repeats may be present for many selective purposes such as antigen
variation or gene dosage. Hence, a trade-off exists between the
advantages of having the potential for sequence variation and the
disadvantages it produces, by stimulating rearrangements that disrupt
the chromosomal structure. For example, we observed that repeats tend
to be placed in the chromosome in such a way that the rearrangements
they may induce provoke smaller disruptions to the chromosomal
replication structure than expected by chance. Further, there is an
important negative correlation between the number of repeats and the
replication strand biases or gene order conservation. In short, this is
a talk on replication and repeats, but especially on order and disorder
in bacterial genomes.


Last update: December 03, 2004