Sequence Analysis I, Sun., January 21, 20:30-21:30 Multiple Alignment by Sequence Annealing Ariel S. Schwartz, EECS Computer Science Division, UC Berkeley, USA Lior Pachter, Department of Mathematics, UC Berkeley, USA Abstract: Motivation: We introduce a novel approach to multiple alignment that is based on an algorithm for rapidly checking whether single matches are consistent with a partial multiple alignment. This leads to a sequence annealing algorithm, which is an incremental method for building multiple sequence alignments one match at a time. Our approach improves significantly on the standard progressive alignment approach to multiple alignment. Results: The sequence annealing algorithm performs well on benchmark test sets of protein sequences. It is not only sensitive, but also specific, drastically reducing the number of incorrectly aligned residues in comparison to other programs. The method allows for adjustment of the sensitivity/specificity tradeoff, and can be used to reliably identify homologous regions among protein sequences. Availability: An implementation of the sequence annealing algorithm is available at http://bio.math.berkeley.edu/amap/ Tandem Repeats over the Edit Distance Dina Sokol and Justin Tojeira, Brooklyn College of the City University of New York, USA Gary Benson, Boston University, USA Abstract: A tandem repeat in DNA is a sequence of two or more contiguous, approximate copies of a pattern of nucleotides. Tandem repeats occur in the genomes of both eukaryotic and prokaryotic organisms. They are important in numerous fields including disease diagnosis, mapping studies, human identity testing (DNA fingerprinting), sequence homology, and population studies. Although tandem repeats have been used by biologists for many years, there are few tools available for performing an exhaustive search for all tandem repeats in a given sequence. In this paper we describe an efficient algorithm for finding all tandem repeats within a sequence, under the edit distance measure. The contributions of this paper are two-fold: theoretical and practical. We present a precise definition for tandem repeats over the edit distance, and an efficient, deterministic algorithm for finding these repeats. The algorithm has been implemented in C++, and a website for the program is under construction. The use of this tool will assist biologists in discovering new ways that tandem repeats affect both the structure and function of DNA and protein molecules. Molecular Recognition and Computer Aided Drug Design, Mon., January 22, 10:00-11:30 Analysis of Binding Site Similarity, Small-Molecule Similarity and Experimental Binding Profiles in the Human Cytosolic Sulfotransferase Family Rafael J. Najmanovich, European Bioinformatics Institute (EMBL-EBI), UK and Structural Genomics Consortium, University of Toronto, Canada Richard J. Morris and Janet M. Thornton, European Bioinformatics Institute (EMBL-EBI), UK Abdellah Allali-Hassani, Ludmila Dombrovsky and Masoud Vedadi, Structural Genomics Consortium, University of Toronto, Canada Patricia W. Pan, Medical Biophysics Department and Structural Genomics Consortium, University of Toronto, Canada Alexander N. Plotnikov, Physiology Department and Structural Genomics Consortium, University of Toronto, Canada Aled Edwards and Cheryl Arrowsmith, Structural Genomics Consortium and Banting & Best Department of Medical Research, University of Toronto, Canada Abstract: Motivation: In the present work we combine computational analysis and experimental data to explore the extent to which binding site similarities between members of the human cytosolic sulfotransferase family correlate with small-molecule binding profiles. Conversely, from a small-molecule point of view, we explore the extent to which structural similarities between small--molecules correlate to protein binding profiles. Results: The comparison of binding site structural similarities and small-molecule binding profiles shows that proteins with similar small-molecule binding profiles tend to have a higher degree of binding site similarity but the later is not sufficient to predict small-molecule binding patterns, highlighting the difficulty of predicting small-molecule binding patterns from sequence or structure. Likewise, from a small-molecule perspective, small-molecules with similar protein binding profiles tend to be topologically similar but topological similarity is not sufficient to predict their protein binding patterns. These observations have important consequences for function prediction and drug design. Electrostatic Potentials of Proteins in Water: A Structured Continuum Approach Andreas Hildebrandt and Hans-Peter Lenhof, Center for Bioinformatics, Saarland University, Germany Ralf Blossey, Interdisciplinary Research Institute Lille, Germany Sergej Rjasanow, Dept. of Mathematics, Saarland University, Germany Oliver Kohlbacher, Dept. for Simulation of Biological Systems, University Tübingen, Germany Abstract: Electrostatic interactions play a crucial role in many biomolecular processes, including molecular recognition and binding. Biomolecular electrostatics is modulated to a large extent by the water surrounding the molecules. Here, we present a novel approach to the computation of electrostatic potentials which allows the inclusion of water structure into the classical theory of continuum electrostatics. Based on our recent purely differential formulation of nonlocal electrostatics (Hildebrandt et al., Phys. Rev. Lett. {\bf 93} (2004) 108104) we have developed a new algorithm for its efficient numerical solution. The key component of this algorithm is a boundary element solver, having the same computational complexity as established boundary element methods for local continuum electrostatics. This allows, for the first time, the computation of electrostatic potentials and interactions of large biomolecular systems immersed in water including effects of the solvent's structure in a continuum description. We illustrate the applicability of our approach with two examples, the enzymes trypsin and acetylcholinesterase (AChE). The approach is applicable to all problems requiring precise prediction of electrostatic interactions in water, such as protein-ligand and protein-protein docking, folding, and chromatin regulation. Initial results indicate that this approach may shed a new light on biomolecular electrostatics and on aspects of molecular recognition that classical local electrostatics cannot reveal. EBIMed - Text Crunching to Gather Facts for Proteins from Medline Dietrich Rebholz-Schuhmann, Harald Kirsch, Miguel Arregui, Sylvain Gaudan, Mark Riethoven, and Peter Stoehr, European Bioinformatics Institute, UK Abstract: To allow efficient and systematic retrieval of statements from Medline, we have developed EBIMed, a service that combines document retrieval with co-occurrence-based analysis of Medline abstracts. Upon keyword query, EBIMed retrieves the abstracts from EMBL-EBI's installation of Medline and filters for sentences that contain biomedical terminology maintained in public bioinformatics resources. The extracted sentences and terminology are used to generate an overview table on proteins, GO annotations, drugs and species used in the same biological context. All terms in retrieved abstracts and extracted sentences are linked to their entries in biomedical databases. We assessed the quality of the identification of terms and relations in the retrieved sentences. More than 90% of the protein names found indeed represented a protein. According to the analysis of 4 protein/protein pairs from the Wnt pathway we estimated that 37% of the statements containing such a pair mentioned a meaningful interaction and clarified the interaction of Dkk with LRP. We conclude that EBIMed improves access to information where proteins and drugs are involved in the same biological process, e.g. statements with GO annotations of proteins, protein/protein interactions and effects of drugs on proteins. Access: http://www.ebi.ac.uk/Rebholz-srv/ebimed Computational Genomics I, Mon., January 22, 12:00-14:00 Optimization of Probe Coverage for High-Resolution Oligonucleotide aCGH Doron Lipson, Computer Science Dept., Technion, Israel Zohar Yakhini, Agilent Technologies, Israel Yonatan Aumann, Computer Science Dept., Bar-Ilan University, Israel Abstract: Motivation: The resolution at which genomic alterations can be mapped by means of oligonucleotide aCGH (array-based Comparative Genomic Hybridization) is limited by two factors: the availability of high-quality probes for the the target genomic sequence and the array real-estate. Optimization of the probe selection process is required for arrays that are designed to probe specific genomic regions in very high resolution without compromising probe quality constraints. Results: In this paper we describe a well-defined optimization problem associated with the problem of probe selection for high-resolution aCGH arrays. We propose the "whenever possible epsilon-cover" as a formulation that faithfully captures the requirement of probe selection problem, and provide a fast randomized algorithm that solves the optimization problem in O(n log n) time, as well as a deterministic algorithm with the same asymptotic performance. We apply the method in a typical high-definition array design scenario and demonstrate its superiority with respect to alternative approaches. Simultaneous Alignment and Annotation of cis-Regulatory Regions Abha Singh Bais, Steffen Grossmann, and Martin Vingron, Max Planck Institute for Molecular Genetics, Germany Abstract: Motivation: Current methods that annotate conserved transcription factor binding sites in an alignment of two regulatory regions perform the alignment and annotation step separately and combine the results in the end. If the site descriptions are weak or the sequence similarity is low, the local gap structure of the alignment poses a problem in detecting the conserved sites. It is therefore desirable to have an approach that is able to simultaneously consider the alignment as well as possibly matching site locations. Results: With SimAnn we have developed a tool that serves exactly this purpose. By combining the annotation step and the alignment of the two sequences into one algorithm, it detects conserved sites more clearly. It has the additional advantage that all parameters are calculated based on statistical considerations.  This allows for its successful application with any binding site model of interest.  We present the algorithm and the approach for parameter selection and compare its performance with that of other, non-simultaneous methods on both simulated and real data. Availability: A command-line based C++ implementation of SimAnn is available from the authors upon request. Additionally, we provide Perl scripts for calculating the input parameters based on statistical considerations. Genetic Code Symmetry and Efficient Design of GC-Constrained Coding Sequences Matan Gavish, School of Physics, Tel Aviv University, Israel Amnon Peled, Goldyne Savad Gene Therapy Institute, Hadassah, Israel Benny Chor, School of Computer Science, Tel Aviv University, Israel Abstract: Motivation: Cloning of long DNA sequences (40-60 bases) into phage display libraries using PCR is a low efficiency process, in which PCR is used to incorporate a DNA insert, coding for a certain peptide, into the amplified sequence. The PCR efficiency in this process is strongly affected by the distribution of G-C bases in the amplified sequence. As any DNA insert coding for the target peptide may be attempted, there is a flexibility in choosing part of the amplified sequence. Since the number of inserts coding for the same peptide is exponential in the peptide length, a computational problem naturally arises - that of efficiently finding an insert, whose parameters are optimal for PCR cloning. Results: The GC distribution requirements are formulated as a search problem. We developed an efficient, linear time “one pass” algorithm for this problem. Interestingly, our algorithm strongly relies on a novel symmetry, which we discovered in the standard genetic code. Most nonstandard genetic codes examined possess this symmetry as well, yet some do not. We generalize the search problem and consider the case of a nonstandard, or arbitrary, genetic code where this symmetry does not necessary hold. We solve the generalized problem in polynomial, but non-linear, time. Discovering Tightly Regulated and Differentially Expressed Gene Sets in Whole Genome Expression Data Chun Ye and Eleazar Eskin, University of California, San Diego, USA Abstract: Motivation: Recently, a new type of expression data is being collected which aims to measure variation of pathways due to genetic variation. In these datasets, expression profiles are constructed for multiple strains of the same model organism under the same condition. The goal of analyses of this data is to find differences in regulatory patterns due to genetic variation between strains, often without a phenotype of interest in mind. We present a new method based on notions of correlated expression and differential expression to look for significant sets of genes. Results: When we use categorical phenotype information, as in the Alzheimer's and diabetes datasets, our method finds many of the same gene sets as GSEA. But the notion of correlated gene sets allows us to focus our efforts on biological processes subjected to tight regulation. In murine hematopoietic stem cells, we are able to discover significant gene sets independent of a phenotype of interest. Some of these gene sets are associated with several blood related phenotypes. Networks, Pathways and Systems, Mon., January 22, 15:30-18:00 Biological Network Comparison using Graphlet Degree Distribution Natasa Przulj, Computer Science Department, University of California, Irvine, USA Abstract: Motivation: Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. Results: We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes "touching'' k edges, into distributions measuring the number of nodes "touching'' k "graphlets'', where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 "graphlet degree distributions'' of graphlets with 2, 3, 4, and 5 nodes, but it is easily extendible to a greater number of constraints (i.e, graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network "agreement'' measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the fourteen eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erdos-Renyi, random scale-free, or Barabasi-Albert scale-free networks. Availability: Software executables are available upon request. Identification of Conserved Protein Complexes Based on a Model of Protein Network Evolution Eitan Hirsh and Roded Sharan, School of Computer Science, Tel Aviv University, Israel Abstract: Motivation: Data on protein-protein interactions are increasing exponentially. To date, large scale protein interaction networks are available for human and most model species. The arising challenge is to organize these networks into models of cellular machinery. As in other biological domains, a comparative approach provides a powerful basis for addressing this challenge. Results: We develop a probabilistic model for protein complexes that are conserved across two species. The model describes the evolution of conserved protein complexes from an ancestral species by protein interaction attachment and detachment and gene duplication events. We apply our model to search for conserved protein complexes within the protein-protein interaction networks of yeast and fly, which are the largest networks in public databases. We detect 150 conserved complexes that match well known complexes in yeast and are coherent in their functional annotations both in yeast and in fly. In comparison to two previous approaches, our model yields higher specificity and sensitivity levels in protein complex detection. Phylogenetic Reconstruction from Non-Genomic Data Jose C. Clemente and Kenji Satou, Japan Advanced Institute of Science and Technology, Japan Gabriel Valiente, Technical University of Catalonia, Spain Abstract: Recent results related to horizontal gene transfer suggest that phylogenetic reconstruction cannot be determined conclusively from sequence data, resulting in a shift from approaches based on polymorphism information in DNA or protein sequence to studies aimed at understanding the evolution of complete biological processes. The increasing amount of available information on metabolic pathways for several species makes it of greater relevance to understand the similarities and differences among such pathways. These similarities can then be used to infer phylogenetic trees not based exclusively in sequence data, therefore avoiding the previously mentioned problems. In this paper, we present a method to assess the structural similarity of metabolic pathways for several organisms. Our algorithms work by using one of three possible enzyme similarity measures (hierarchical, information content, gene ontology), and one of two clustering methods (neighbor-joining, unweighted pair group method with arithmetic mean), to produce a phylogenetic tree both in Newick and graphic format. The web server implementing our algorithms is optimized to answer queries in linear time. The software is available for free public use on a web server, at the contact address. It is available on demand in source code form for research use to educational institutions, non-profit research institutes, government research laboratories, and individuals, for non-exclusive use, without the right of the licensee to further redistribute the source code. Similarities and Differences of Gene Expression in Yeast Stress Conditions Oleg Rokhlenko and Ydo Wexler, Computer Science Dept., Technion, Israel Zohar Yakhini, Agilent Technologies, Israel Abstract: Motivation and Methods: All living organisms and the survival of all cells critically depend on their ability to sense and quickly adapt to changes in the environment and to other stress conditions. We study stress response mechanisms in Saccharomyces cerevisiae by identifying genes that, according to very stringent criteria, have persistent co-expression under a variety of stress conditions. This is enabled through a fast clique search method applied to the intersection of several co-expression graphs calculated over the data of Gasch et al. [3]. This method exploits the topological characteristics of these graphs. Results: We observe cliques in the intersection graphs that are much larger than expected under a null model of changing gene identities for different stress conditions but maintaining the co-expression topology within each one. Persistent cliques are analyzed to identify enriched function as well as enriched regulation by a small number of TFs. These TFs therefore characterize a universal and persistent reaction to stress response. We further demonstrate that the vertices (genes) of many cliques in the intersection graphs are colocalized in the yeast genome, to a degree far beyond the random expectation. Co-localization can hypothetically contribute to a quick co-ordinated response. We propose the use of persistent cliques in further study of properties of co-regulation. Efficient Inference on Phylogenetic Trees Using Poisson Regression Saharon Rosset, IBM T. J. Watson Research Center, USA Abstract: We suggest the use of Poisson regression for time inference and hypothesis testing on a bifurcating Phylogenetic tree with known topology. This method is computationally simple and naturally accommodates variable substitution rates across different sites, without requiring estimation of these rates. We identify the assumptions under which this is a maximum likelihood inference approach and show that in some realistic situations --- in particular, when the probability of repeated mutation within each branch of the tree is small --- these assumptions hold with high probability. Our motivating domain is human mitochondrial DNA trees, and we illustrate our method on a problem of estimating the time to most recent common ancestor of all non-African mtDNA, using publicly available data. We test for molecular clock violations using multiple comparisons, and conclude that the global molecular clock hypothesis cannot be rejected based on this data. Structural Bioinformatics I, Tue., January 23, 10:00-11:30 Vorolign - Fast Structural Alignment Using Voronoi Contacts Fabian Birzele, Jan Erik Gewehr, Gergely Csaba, and Ralf Zimmer, Practical Informatics and Bioinformatics Group, LMU Munich, Germany Abstract: Summary: Vorolign, a fast and flexible structural alignment method for two or more protein structures is introduced. The method aligns protein structures using double dynamic programming and measures the similarity of two residues based on the evolutionary conservation of their corresponding Voronoi-contacts in the protein structure. This similarity function allows to align protein structures even in cases where structural flexibilities exist. Multiple structural alignments are generated from a set of pairwise alignments using a consistency-based, progressive multiple alignment strategy. Results: The performance of Vorolign is evaluated for several different applications of protein structure comparison, including automatic family detection as well as pairwise and multiple structure alignment. Vorolign accurately detects the correct family, superfamily or fold of a protein with respect to the SCOP classification on a set of difficult target structures. A scan against a database of 4358 proteins takes on average 1 minute per target. The performance of Vorolign in calculating pairwise and multiple alignments is found to be comparable to other pairwise and multiple protein structure alignment methods. Availability: Vorolign is freely available for academic users as a Web server at http://www.bio.ifi.lmu.de/Vorolign Prediction and Simulation of Motion in Pairs of Transmembrane Alpha-Helices Angela Enosh, Sarel J. Fleishman, Nir Ben-Tal, and Dan Halperin, Tel Aviv University, Israel Abstract: Motivation: Motion in transmembrane-proteins plays an essential role in a variety of biological phenomena, including signal transduction, transport of metabolites, ligand binding and molecular recognition of hormones and neurotransmitters. Thus, developing an automated method for predicting and simulating motion in this class of proteins should result in an increased level of understanding of their biochemical mechanisms. We have developed an algorithm for predicting and simulating motion in transmembrane (TM) proteins. We used probabilistic motion-planning techniques to sample possible motion paths. For each conformation we computed the buried-surface area between the helices, providing a rudimentary assessment of the free-energy of helix association. Our algorithm considers a wide range of degrees of freedom (dofs) involved in the motion, including external and internal moves. However, in order to handle the vast dimensionality of the problem, we employed some relaxations on these dofs in a way that is unlikely to demolish the native motion that the protein undergoes. Results: Overexpression of the receptor tyrosine kinase (RTK) ErbB2 was implicated in causing a variety of human cancers. Recently, a molecular mechanism for rotation-coupled activation of the receptor was suggested. We applied our algorithm to investigate the TM domain of this protein, and compared our results to this mechanism. Our algorithm yielded several motion pathways and among them a motion similar to the proposed mechanism was ranked first. Our algorithm simulates the motion including all the dofs involved in this process and can automatically produce movies that demonstrate such motions. Rediscovering Secondary Structures as Network Motifs - An Unsupervised Learning Approach Barak Raveh, Ofer Rahat, Ronen Basri, and Gideon Schreiber, Weizmann Institute of Science, Israel Abstract: Motivation: Secondary structures are key descriptors of a protein fold and its topology. In recent years, they facilitated intensive computational tasks for finding structural homologues, fold prediction and protein design. Their popularity stems from an appealing regularity in patterns of geometry and chemistry. However, the definition of secondary structures is of subjective nature. An unsupervised de-novo discovery of these structures would shed light on their nature, and improve the way we use these structures in algorithms of structural bioinformatics. Methods: We developed a new method for unsupervised partitioning of undirected graphs, based on patterns of small recurring network motives. Our input was the network of all H-bonds and covalent interactions of protein backbones. This method can be also used for other biological and non-biological networks. Results: In a fully unsupervised manner, and without assuming any explicit prior knowledge, we were able to rediscover the existence of conventional alpha-helices, parallel beta-sheets, anti-parallel sheets and loops, as well as various non-conventional hybrid structures. The relation between connectivity and crystallographic temperature factors establishes the existence of novel secondary structures. Contact: barak.raveh@weizmann.ac.il Structural Bioinformatics II, Tue., January 23, 12:00-14:00 A Tale of Two Tails: Why are Terminal Residues of Proteins Exposed? Etai Jacob and Ron Unger, Faculty of Life Sciences, Bar Ilan University, Israel Abstract: Motivation: It is widely known that terminal residues of proteins (i.e. the N and C termini) are predominantly located on the surface of proteins and exposed to the solvent. However, there is no good explanation as to the forces driving this phenomenon. The common explanation that terminal resi-dues are charged, and charged residues prefer to be on the surface, can not explain the magnitude of the phenomenon. Here, we survey a large number of proteins from the PDB in order to explore, quantitatively, this phenomenon, and then we use a lattice model to study the mechanisms involved. Results: The location of the termini was examined for 425 small monomeric proteins (50-200 AA) and it was found that the average solvent accessibility of termini residues is 87.1% compared with 49.2% of charged residues and 35.9% of all residues. Using a cutoff of 50% of the maximal possible exposure, 80.3% of the N-terminal and 86.1% of the C-terminal residues are exposed compared to 32% for all residues. In addition, terminal residues are much more distant from the center of mass of their proteins than other residues. Using a 2D lattice, a large population of model proteins was studied on three levels: structural selection of compact structures, thermodynamic selection of conformations with a pronounced energy gap, and kinetic selection of fast folding proteins using Monte-Carlo simulations. Progressively, each selection raises the proportion of proteins with termini on the surface, resulting in similar proportions to those observed for real proteins. A Novel Pattern Recognition Algorithm to Classify Membrane Protein Unfolding Pathways with High-Throughput Single Molecule Force Spectroscopy Annalisa Marsico, Dirk Labudde, Tanuj Sapra, Daniel Muller, and Michael Schroeder, Biotechnologisches Zentrum der TU Dresden, Germany Abstract: Motivation: Misfolding of membrane proteins plays an important role in many human diseases such as retinitis pigmentosa, hereditary deafness, and diabetes insipidus. Little is known about membrane proteins as there are only a very few high-resolution structures. Single molecular force spectroscopy is a novel technique, which measures the force necessary to pull a protein out of a membrane. Such force curves contain valuable information on the protein's structure, conformation, and inter- and intra-molecular forces. High-throughput force spectroscopy experiments generate hundreds of force curves including spurious ones and good curves, which correspond to different unfolding pathways. Manual analysis of these data is a bottleneck and source of inconsistent and subjective annotation. Results: We propose a novel algorithm for the identification of spurious curves and curves representing different unfolding pathways. Our algorithm proceeds in three stages: First, we reduce noise in the curves by applying dimension reduction; second, we align the curves with dynamic programming and compute pairwise distances; third, we cluster the curves based on these distances. We apply our method to a hand curated dataset of 135 force curves of bacteriorhodopsin mutant P50A. Our algorithm achieves a success rate of 81% distinguishing spurious from good curves and a success rate of 76% classifying unfolding pathways. As a result, we discuss five different unfolding pathways of bacteriorhodopsin including three main unfolding events and several minor ones. Finally, we link folding barriers to the degree of conservation of residues. Overall, the algorithm tackles the force spectroscopy bottleneck and leads to more consistent and reproducible results paving the way for high-throughput analysis of structural features of membrane proteins. Using an Alignment of Fragment Strings for Comparing Protein Structures Iddo Friedberg, Tim Harder, Zhanwen Li, and Adam Godzik, Burnham Institute for Medical Research, USA Rachel Kolodny, Columbia University and Howard Hughes Medical Institute, USA Einat Sitbon, Weizmann Institute of Science, Israel Abstract: Motivation: Most methods which are used to compare protein structures use 3D structural information to do so. At the same time, it has been shown that a 1D string representation of local protein structure retains a degree of structural information. This type of representation can be a powerful tool for protein structure comparison and classification, given the arsenal of sequence comparison tools developed by computational biology. However, in order to do so, there is a need to first understand how much information is contained in various possible 1D representations of protein structure. Results: Here we describe the use of a particular structure fragment library, denoted here as KL strings, for the 1D representation of protein structure. Using KL strings, we develop an infrastructure for comparing protein structures with a 1D representation. This study focuses on the added value gained from such a description. We show the new local structure language adds resolution to the traditional three state (helix, strand and coil) secondary structure description, and provides a high degree of accuracy in recognizing structural similarities when used with a pairwise alignment benchmark. The results of this study have immediate applications towards fast structure recognition, and for fold prediction and classification. Supplementary material: http://iddo-friedberg.org/ECCB06-supplement ISIS: Interaction Sites Identified from Sequence Yanay Ofran and Burkhard Rost, Columbia University, USA Abstract: Motivation: Large-scale experiments reveal pairs of inter-acting proteins but leave the residues involved in the inter-actions unknown. These interface residues are essential for understanding the mechanism of interaction and are often desired drug targets. Reliable identification of residues that reside in protein-protein interface typically requires analysis of protein structure. Therefore, for the vast majority of pro-teins, for which there is no high resolution structure, there is no effective way of identifying interface residues. Results: Here, we present a knowledge-based method that identifies interacting residues from sequence. The method is based on a detailed characterization of protein-protein inter-faces in known high-resolution complexes. We use pre-dicted structural features and evolutionary information, combined with the sequence of the protein. Our strongest predictions reached above 90% accuracy in a cross-validation experiment. Our results suggested that despite the significant diversity in the nature of protein-protein interac-tions, they all share common basic principles identifiable even at the sequence level. Sequence Analysis II, Tue., January 23, 15:30-17:30 Incremental Window-Based Protein Sequence Alignment Algorithms Huzefa Rangwala and George Karypis, Department of Computer Science and Engineering, University of Minnesota-Twin Cities, USA Abstract: Motivation: Protein sequence alignment plays a critical role in computational biology as it is an integral part in many analysis tasks designed to solve problems in compartive genomics, structure and function prediction, and homology modeling. Methods: We have developed novel sequence alignment algorithms that compute the alignment between a pair of sequences based on short fixed- or variable-length highscoring subsequences. Our algorithms build the alignments by repeatedly selecting the highest scoring pairs of subsequences and using themto construct small portions of the final alignment. We utilize PSI-BLAST generated sequence profiles and employ a profile-to-profile scoring scheme derived from PICASSO. Results: We evaluated the performance of the computed alignments on two recently published benchmark datasets and compared them against the alignments computed by existing state-of-the-art dynamic programming-based profile-to-profile local and global sequence alignment algorithms. Our results show that the new algorithms achieve alignments that are comparable or better to those achieved by existing algorithms. Moreover, our results also showed that these algorithms can be used to provide better information as to which of the aligned positions are more reliable - a critical piece of information for comparative modeling applications. Designing Patterns for Profile HMM Search Yanni Sun and Jeremy Buhler, Washington University in Saint Louis, USA Abstract: Motivation: Profile HMMs are a powerful tool for modeling conserved motifs in proteins. These models are widely used by search tools to classify new protein sequences into families based on domain architecture. However, the proliferation of known motifs and new proteomic sequence data poses a computational challenges for search, potentially requiring days of CPU time to annotate an organism's proteome. Results: We use PROSITE-like patterns as a filter to speed up the comparison between protein sequence and profile HMM. A set of patterns is designed starting from the HMM, and only sequences matching one of these patterns are compared to the HMM by full dynamic programming. We give an algorithm to design patterns with maximal sensitivity subject to a bound on the false positive rate. Experiments show that our patterns typically retain at least 90% of the sensitivity of the source HMM while accelerating search by an order of magnitude. Simulating Multiplexed SNP Discovery Rates using Base-Specific Cleavage and Mass Spectrometry Sebastian Böcker, Bielefeld University, Germany Abstract: Single Nucleotide Polymorphisms (SNPs) are believed to contribute strongly to the genetic variability in living beings, and SNP and mutation discovery is of great interest in today's Life Sciences. A comparatively new method to discover such polymorphisms is based on base-specific cleavage, where resulting cleavage products are analyzed by mass spectrometry. One particular advantage of this method is the possibility of multiplexing the biochemical reactions, that is, examining multiple genomic regions in parallel. Simulations can help estimating the performance of a method for polymorphism discovery, and allow us to evaluate the influence of method parameters on the discovery rate, and also to investigate whether the method is well-suited for a certain genomic region. We show how to efficiently conduct such simulations for polymorphism discovery using base-specific cleavage and mass spectrometry. Simulating multiplexed polymorphism discovery leads us to the problem of uniformly drawing a multiplex: Given a multiset of natural numbers we want to uniformly draw a subset of fixed cardinadinality so that the elements sum up to some fixed total length. We show how to enumerate multiplex layouts using dynamic programming what allows us to uniformly draw a multiplex. Learning Probabilistic Models of cis-Regulatory Modules that Represent Logical and Spatial Aspects Keith Noto and Mark Craven, University of Wisconsin, Madison, USA Abstract: Motivation: The process of transcription is controlled by systems of factors which bind in a specific arrangement, called a {\em cis-regulatory module} (CRM), in a set of promoter regions. We present a discriminative learning algorithm which simultaneously learns the DNA binding site motifs as well as the logical structure and spatial aspects of a CRM. Results: Our results on yeast data sets show better predictive accuracy than a current state-of-the-art approach on the same data sets. Our results on yeast, fly, and human data sets show that the inclusion of logical and spatial aspects improve the predictive accuracy of our learned models. Availability: Source code will be made available at: http://www.biostat.wisc.edu Contact: noto@cs.wisc.edu Proteomics, Wed., January 24, 10:00-11:30 TOPP - The OpenMS Proteomics Pipeline Oliver Kohlbacher, Nico Pfeifer, and Marc Sturm, Universität Tübingen, Germany Knut Reinert, Clemens Gröpl, and Eva Lange, Freie Universität Berlin, Germany Ole Schulz-Trieglaff, Freie Universität Berlin / Max Planck Research School for Computational Biology, Germany Abstract: Motivation: Experimental techniques in proteomics have seen rapid development over the last few years. Volume and complexity of the data have both been growing at a similar rate. Accordingly, data management and analysis are one of the major challenges in proteomics. Flexible algorithms are required to handle changing experimental setups and to assist in developing and validating new methods. In order to facilitate these studies, it would be desirable to have a flexible 'toolbox' of versatile and user-friendly applications allowing for rapid construction of computational workflows in proteomics. Results: We describe a set of tools for proteomics data analysis -- TOPP, The OpenMS Proteomics Pipeline. TOPP provides a set of computational tools which can be easily combined into analysis pipelines even by non-experts and can be used in proteomics workflows. These applications range from useful utilities (file format conversion, peak picking) over wrapper applications for known applications (e.g. Mascot) to completely new algorithmic techniques for data eduction and data analysis. We anticipate that TOPP will greatly facilitate rapid prototyping of proteomics data evaluation pipelines. As such, we describe the basic concepts and the current abilities of TOPP and illustrate these concepts in the context of two example applications: the identification of peptides from a raw data set through database search and the complex analysis of a standard addition experiment for the absolute quantitation of biomarkers. The latter example demonstrates TOPP's ability to construct flexible analysis pipelines in support of complex experimental setups. Availability: The TOPP components are available as open-source software under the lesser GNU public license (LGPL). Source code is available from the project web site at www.OpenMS.de Difference Detection in LC-MS Data for Protein Biomarker Discovery Jennifer Listgarten and Sam T. Roweis, Department of Computer Science, University of Toronto, Canada Radford M. Neal, Department of Statistics and Department of Computer Science, University of Toronto, Canada Peter Wong and Andrew Emili, Banting and Best Department of Medical Research, University of Toronto, Canada Abstract: Motivation: There is a pressing need for improved proteomic screening methods allowing for earlier diagnosis of disease, systematic monitoring of physiological responses, and the uncovering of fundamental mechanisms of drug action. The combined platform of LC-MS (Liquid-Chromatography-Mass-Spectrometry) has shown promise in moving toward a solution in these areas. In this paper we present a technique for discovering differences in protein signal between two classes of samples of LC-MS serum proteomic data without use of tandem mass spectrometry, gels, or labelling. This method works on data from a lower-precision MS instrument, the type routinely used by and available to the community at large today. We test our technique on a controlled (spike-in) but realistic (serum biomarker discovery) experiment which is therefore verifiable. We also develop a new method for helping to assess the difficulty of a given spike-in problem. Lastly, we show that the problem of class prediction, sometimes mistaken as a solution to biomarker discovery, is actually a much simpler problem. Results: Using precision-recall curves with experimentally extracted ground truth, we show that i) our technique has good performance using 7 replicates from each class, ii) performance degrades with decreasing number of replicates, iii) the signal that we are teasing out is not trivially available (i.e., the differences are not so large that the task is easy). Lastly, we easily obtain perfect classification results for data in which the problem of extracting differences does not produce absolutely perfect results. This emphasizes the different nature of the two problems and also their relative difficulties. Availability Our data is publically available as a benchmark for further studies of this nature, along with supplementary information, at http://www.cs.toronto.edu/~jenn/LCMS.html. Identifying HLA Supertypes by Learning Distance Functions Tomer Hertz and Chen Yanover, Hebrew University of Jerusalem, Israel Abstract: The development of epitope-based vaccines crucially relies on the ability to classify Human Leukocyte Antigen (HLA) molecules into sets that have similar peptide binding specificities, termed supertypes. In their seminal work, Sette and Sidney defined 9 HLA class I supertypes, and claimed that  these provide an almost perfect coverage of the entire repertoire of HLA class I molecules. HLA alleles are highly polymorphic and polygenic and therefore experimentally classifying each of these molecules to supertypes is at present an impossible task. Recently, a number of computational methods have been proposed for this task. These methods are based on defining protein similarity measures, derived from analysis of binding peptides or from analysis of the proteins themselves. In this paper we define both peptide derived and protein derived similarity measures, which are based on learning distance functions. The peptide driven measure is defined using a peptide-peptide distance function, which is learnt using information about known binding and non-binding peptides. The protein similarity measure is defined using a protein-protein distance function, which is learnt using information about alleles previously classified into supertypes by Sette and Sidney. We compare the classification obtained by these two complimentary methods to previously suggested classification methods. In general, our results are in excellent agreement with the classifications suggested by Sette and Sidney and with those reported by Lund et. al. There are two important advantages of our proposed distance-based approach. First, it makes use of two different and important immunological sources of information -- HLA alleles and peptides that are known to bind or not bind to these alleles. Second, since each of our distance measures is trained using a different source of information, their combination can provide a more confident classification of alleles into supertypes. Comparative and Computational Genomics, Wed., January 24, 12:00-14:00 A Comparative Genome Approach to Marker Ordering Thomas Faraut, Simon de Givry, Patrick Chabrier, and Thomas Schiex, INRA, France Thomas Derrien, Francis Galibert, and Christophe Hitte, CNRS-Université de Renes 1, France Abstract: Motivation: Genome maps are fundamental to the study of an organism and essential in the process of genome sequencing which in turn provides the ultimate map of the genome. The increased number of genomes being sequenced offers new opportunities for the mapping of closely related organisms. We propose here an algorithmic formalization of a genome comparison approach to marker ordering. Results: In order to integrate a comparative mapping approach in the algorithmic process of map construction and selection, we propose to extend the usual statistical model describing the experimental data, here radiation hybrids (RH) data, in a statistical framework that models additionally the evolutionary relationships between a proposed map and a reference map: an existing map of the corresponding orthologous genes or markers in a closely related organism. This has concretely the effect of exploiting, in the process of map selection, the information of marker adjacencies in the related genome when the information provided by the experimental data is not conclusive for the purpose of ordering. In order to compute efficiently the map, we proceed to a reduction of the maximum likelihood estimation to the Traveling Salesman Problem. Experiments on simulated RH data sets as well as on a real RH data set from the canine RH project show that maps produced using the likelihood defined by the new model are significantly better than maps built using the traditional RH model. Family Relationships: Should Consensus Reign?-Consensus Clustering for Protein Families Macha Nikolski and David James Sherman, CNRS/LaBRI, Université Bordeaux 1, France Abstract: Motivation: Reliable identification of protein families is key to phylogenetic analysis, functional annotation and the exploration of protein function diversity in a given phylogenetic branch. As more and more complete genomes are sequenced, there is a need for powerful and reliable algorithms facilitating protein families fabrication. Results: We have formulated the problem of protein families construction as an instance of consensus clustering, for which we designed a novel algorithm that is computationally efficient in practice and produces high quality results. Our algorithm uses an election method to construct consensus families from competing clustering computations. Our consensus clustering algorithm is tailored to serve the specific needs of comparative genomics projects. First, it provides a robust means to incorporate results from different and complementary clustering methods, thus avoiding the need for an a priori choice that may introduce computational bias in the results. Second, it is suited to large-scale projects due to the practical efficiency. And third, it produces high quality results where families tend to represent groupings by biological function. Availability: This method has been used for Genolevures project to compute protein families of Hemiascomycetous yeasts. The data is available online at http://cbi.labri.fr/Genolevures/fam/ Merging Microarray Cell Synchronization Experiments through Curve Alignment Filip Hermans and Elena Tsiporkova, Dept. of Plant Systems Biology, Flanders Institute for Biotechnology, Belgium Abstract: The validity of periodic cell-cycle regulation studies in plants is seriously compromised by the relatively poor quality of cell synchrony that is achieved for plant suspension cultures in comparison to yeast and mammals. The present state-of-the-art plant synchronization techniques cannot offer a complete cell-cycle coverage and moreover a considerable loss of cell synchrony may occur toward the end of the sampling. One possible solution is to consider combining multiple data sets, produced by different synchronization techniques and thus covering different phases of the cell cycle, in order to arrive at a better cell-cycle coverage. We propose a method that enables pasting expression profiles from different plant cell synchronization experiments and results in an expression curve that spans more than one cell cycle. The optimal pasting overlap is determined via a dynamic time warping alignment. Consequently, the different expression time series are merged together by aggregating the corresponding expression values lying within the overlap area. We demonstrate that the periodic analysis of the merged expression profiles produces more reliable p-values for periodicity. Subsequent Gene Ontology analysis of the results confirms that merging synchronization experiments is a more robust strategy for the selection of potentially periodic genes. Additional validation of the proposed algorithm on yeast data is also presented. A Supervised Approach for Identifying Discriminating Genotype Patterns and its Application to Breast Cancer Data Nir Yosef and Roded Sharan, School of Computer Science, Tel Aviv University, Israel Zohar Yakhini and Anya Tsalenko, Agilent Technologies, Israel Vessela Kristensen, Department of Genetics, Institute of Cancer Research, Rikshospitalet-Radiumhospitalet Medical Center, Montebello, Norway Anne-Lise Børresen-Dale, Department of Genetics, Institute of Cancer Research, Rikshospitalet-Radiumhospitalet Medical Center, Montebello, Norway and Medical Faculty, University of Oslo, Norway Eytan Ruppin, School of Computer Science and School of Medicine, Tel Aviv University, Israel Abstract: Motivation: Large scale association studies, investigating the genetic determinants of a phenotype of interest, are producing increasing amounts of genomic variation data on human cohorts. A fundamental challenge in these studies is the detection of genotypic patterns that discriminate individuals exhibiting the phenotype under study from individuals that do not posses it. The difficulty stems from the large number of single nucleotide polymorphism(SNP) combinations that have to be tested. The discrimination problem becomes even more involved when additional high-throughput data, such as gene expression data, is available for the same cohort. Results: We have developed a graph theoretic approach for identifying discriminating patterns for a given phenotype in a genotyped population. The method is based on representing the SNP data as a bipartite graph of individuals and their SNP states, and identifying fully connected subgraphs of this graph that relate individuals enriched for a given phenotypic group. The method can handle additional data types such as expression profiles of the genotyped population. It is reminiscent of biclustering approaches with the crucial difference that its search process is guided by the phenotype under consideration in a supervised manner. We tested our approach in simulations and on real data. In simulations, our method was able to retrieve planted patterns with high success rate. We then applied our approach to a data set of 72 breast cancer patients with available gene expression profiles, genotyped over 695 SNPs. We detected several discriminating patterns thatwere highly significant with respect to various clinical phenotypes, and investigated the groups of patients and the groups of genes they defined. We found the patient groups to be highly enriched for other phenotypes and to display expression coherency among their profiles. The gene groups displayed functional coherency and involved genes with known role in cancer, providing additional support to their involvement. Evolution and Phylogenetics, Wed., January 24, 15:30-17:30 Inferring Phylogeny from Whole Genomes Pawel Gorecki and Jerzy Tiuryn, Warsaw University, Poland Abstract: Motivation: Inferring species phylogenies with a history of gene losses and duplications is a challenging and important task in computational biology. This problem can be solved by duplication-loss models in which the primary step is to reconcile a rooted gene tree with a rooted species tree. Most modern methods of phylogenetic reconstruction (from sequences) produce unrooted gene trees. This limitation leads to the problem of transforming unrooted gene tree into a rooted tree, and then reconciling rooted trees. The main questions are What about biological interpretation of choosing rooting?'', Can we find efficiently the optimal rootings?'', Is the optimal rooting unique?''. Results: In this paper we present a model of reconciling unrooted gene tree with a rooted species tree, which is based on a concept of choosing rooting which has minimal reconciliation cost. Our analysis leads to the surprising property that all the minimal rootings have identical distributions of gene duplications and gene losses in the species tree. It implies, in our opinion, that the concept of an optimal rooting is very robust, and thus biologically meaningful. Also, it has nice computational properties. We present a linear time and space algorithm for computing optimal rooting(s). This algorithm was used in two different ways to reconstruct the optimal species phylogeny of five known yeast genomes from approx. 4700 gene trees. Moreover, we determined locations (history) of all gene duplications and gene losses in the final species tree. It is interesting to notice that the top 5 species trees are the same for both methods. Using Median Sets for Inferring Phylogenetic Trees Matthias Bernt, Daniel Merkle, and Martin Middendorf, University of Leipzig, Germany Abstract: Motivation: Algorithms for phylogenetic tree reconstruction based on gene-order data typically repeatedly solve instances of the Reversal Median problem (RMP) which is to find for three given gene sequences a fourth sequence (called median) with a minimal sum of reversal distances. All existing algorithms of this type consider only one median for each RMP instance even when a large number of medians exist. A careful selection of one of the medians might lead to better phylogenetic trees. Results: We propose a heuristic algorithm amGRP for solving the Multiple Genome Rearrangement Problem (MGRP) by repeatedly solving instances of the RMP taking all medians into account. Algorithm amGRP uses a branch-and-bound method that branches over medians from a selected subset of all medians for each RMP instance. Different heuristics for selecting the subsets have been investigated. To show that the medians for RMP vary strongly with respect to different properties that are likely to be relevant for phylogenetic tree reconstruction, the set of all medians have been investigated for artificial data sets and mitochondrial DNA (mtDNA) sequences. Phylogenetic trees have been computed for a large set of random data sequences and two sets of mtDNA gene-order data for different animal taxa with amGRPg and with two standard algorithms (GRAPPA-DCM and MGR). The results show that amGRP outperforms both other algorithms with respect to solution quality and computation time on the test data. Availability: The source code of amGRP, additional results, and the test instances used in this paper are freely available from the authors of the paper. Efficient Parsimony-Based Methods for Phylogenetic Network Reconstruction Guohua Jin and Luay Nakhleh, Rice University, USA Sagi Snir, University of California, Berkeley, USA Tamir Tuller, Tel Aviv University, Israel Abstract: Phylogenies---the evolutionary histories of groups of organisms---play a major role in representing relationships among biological entities. Although many biological processes can be effectively modeled as a tree-like relationships, others, such as hybrid speciation, and horizontal gene transfer (HGT) result in networks of relationships rather than trees of relationships. Hybrid speciation is a significant evolutionary mechanism in plants, fish, and other groups of species. HGT plays a major role in bacterial genome diversification, and is a significant mechanism by which bacteria develop resistance to antibiotics. Maximum parsimony (MP) is one of the most commonly used criteria for phylogenetic tree inference. Roughly speaking, inference based on this criterion seeks the tree that minimizes the amount of evolution. In 1990, Jotun Hein proposed using this criterion for inferring the evolution of sequences subject to recombination. Preliminary results on small synthetic data sets (Nakhleh et al., 2005) demonstrated the criterion's application to phylogenetic network reconstruction in general, and HGT detection in particular. However, the naive algorithms used by the authors are inapplicable to large data sets due to their demanding computational requirements. Further, no rigorous theoretical analysis of computing the criterion was given, nor was it tested on biological data. In this work, we prove that the problem of scoring the parsimony of a phylogenetic network is NP-hard, and provide an improved fixed parameter tractable algorithm for it. Further, we devise an efficient heuristics for parsimony-based reconstruction of phylogenetic networks. We test our methods on both synthetic and biological data (rbcL gene in bacteria), and obtain very promising results. Phylogeny Reconstruction: Increasing the Accuracy of Pairwise Distance Estimation using Bayesian Inference of Evolutionary Rates Matan Ninio and Nir Friedman, The Hebrew University of Jerusalem, Israel Eyal Privman and Tal Pupko, Tel Aviv University, Israel Abstract: Distance-based methods for phylogeny reconstruction are the fastest and easiest to use, and their popularity is accordingly high. They are also the only known methods that can cope with huge datasets of thousands of sequences. These methods rely on evolutionary distance estimation, and are sensitive to errors in such estimations. In this study, a novel Bayesian method for estimation of evolutionary distances is developed. The proposed method enables the use of a sophisticated evolutionary model that better accounts for among-site rate variation (ASRV), thereby improving the accuracy of distance estimation. Rate variations are estimated within a Bayesian framework by extracting information from the entire dataset of sequences, unlike standard methods that can only use one pair of sequences at a time. We compare the accuracy of a cascade of distance estimation methods, starting from commonly used methods and moving towards the more sophisticated novel method. Simulation studies show significant improvements in the accuracy of distance estimation by the novel method over the commonly used ones. We demonstrate the effect of the improved accuracy on tree reconstruction using both real and simulated protein sequence alignments. Late Breaking Presentations Algorithms on Splicing Graphs for Identifying and Aligning Alternative Splicing Events Michael Sammeth and Sylvain Foissac, Genome Bioinformatics Laboratory, Centre for Genomic Regulation, Catalonia, EU Abstract: The complexity of molecular mechanisms involved in alternative splicing (AS) in literature grows continuously with new studies being published. This data requires an universal way, to describe AS events and to flexibly correlate them with each other. Herein, we describe a method to universally characterize AS events from gene annotations, and an algorithm to align gene structures in order to study the changes of AS events across homologous genes. An online visualization of the proposed methods AStaLaVista is being made available at: http://genome.imim.es/astalavista. Inferring Mechanistic Explanations for Transcription Factor Binding Changes Kenzie MacIsaac and Ernest Fraenkel, Massachusetts Institute of Technology, USA Abstract: We present an algorithm that determines the mechanisms underlying changes in transcriptional regulatory protein binding. The algorithm, called Bluebird, uses a probabilistic approach based on biophysical principles to jointly analyze high-throughput chromatin immunoprecipitation (ChIP-chip) data for multiple proteins in multiple conditions. Bluebird predicts how the observed binding changes are best explained: Do the binding specificities of the proteins change in different conditions? Are binding differences best explained by changes in the nuclear concentration of the proteins? Do several proteins interact? By probabilistically analyzing the raw ChIP-chip data, Bluebird avoids the use of arbitrary thresholds to define bound and unbound genes. Analysis of ChIP-chip data for 37 different yeast transcription factors gave motif predictions consistent with the known binding specificity for all factors. In addition, results for several factors yielded predictions about the underlying mechanism of binding changes between conditions that were in agreement with previously reported experimental results. Reconstructing Sibling Relationships from Microsatellite Data Saad Sheikh, Tanya Berger-Wolf, Bhaskar Dasgupta, and Mary Ashley, University of Illinois at Chicago, USA Wanpracha Chaovalitwongse, Rutgers University, USA Abstract: Reconstruction of sibling relationships from genetic data is an important component of many biological applications. Most current sibship reconstruction methods use statistical and heuristic techniques that rely on a priori knowledge about various parameter distributions. We present a deterministic algorithm that parsimoniously reconstructs sibling groups. We use Mendelian laws of inheritance to generate potential sibling groups. We then optimally select a minimum set of sibling groups necessary to explain the data. We validate our approach using both simulated and real biological data. Refinement and Expansion of Signaling Pathways: The Osmotic Response Network in Yeast Irit Gat-Viks, Tel Aviv University, Israel Abstract: The analysis of large scale genome-wide experiments carries the promise of dramatically broadening our understanding on biological networks. The challenge of systematic integration of experimental results with established biological knowledge on a pathway is still unanswered. Here we present a methodology that attempts to answer this challenge when investigating signaling pathways. We formalize existing qualitative knowledge as a probabilistic model that depicts known interactions between molecules (genes, proteins etc.) as a network and known regulatory relations as logics. We present algorithms that analyze experimental results (e.g., transcription profiles) vis-a-vis the model, and propose improvements to the model based on the fit to the experimental data. These algorithms refine the relations between model components, as well as expand the model to include new components that are regulated by components of the original network. Using our methodology, we have modeled together the knowledge on four established signaling pathways related to osmotic shock response in S. cerevisiae. Using over 100 published transcription profiles, our refinement methodology revealed three cross-talks in the network. The expansion procedure identified with high confidence large groups of genes that are co-regulated by transcription factors from the original network via a common logic. The results reveal a novel delicate repressive effect of the HOG pathway on many transcriptional target genes, and suggest an unexpected alternative functional mode of the MAP kinase Hog1. The analysis also predicts novel feed-forward and feedback loops in the regulatory network, which probably support cellular adaptation to osmotic stress. These results demonstrate that by integrated analysis of data and of well-defined knowledge on signaling pathways, one can generate concrete biological hypotheses about signaling cascades and their downstream regulatory programs. PROMO: A Method for Identifying Modules in Protein Interaction Networks Omer Tamuz, Yaron Singer, and Roded Sharan, Tel Aviv University, Israel Abstract: A major goal of systems biology is the dissection of protein machineries within the cell. The recent availability of genome-scale protein interaction networks provides a key resource for addressing this challenge. Current approaches to the problem are based on devising a scoring scheme for putative protein modules and applying a heuristic search for high-scoring modules. Here we develop a branch and bound approach to perform an exhaustive scan of the search space.We show that such a search is possible and enables detecting modules that are missed by previous approaches. The modules we identify are shown to be significantly coherent in their functional annotations and expression patterns. Our algorithm, PROMO, is shown to outperform the state-of-the-art MCODE and to provide results that are more in line with current biological knowledge. Temporal Aspects of Histone-Modifying Proteins Revealed by Sub-network Analysis Sabine Dietmann, Michael Mader, Hans-Werner Mewes, and Martin Münsterkötter, Institute for Bioinformatics, Germany Abstract: Network analysis has been recently applied to model not only static topological properties, but also temporal aspects of protein complexes on a genomic scale, e.g. during the yeast cell cycle. The topology of transcription factor networks, in particular, has been studied extensively. In eukaryotic genomes, the chromosomal context is crucial for transcriptional activity because of the regulatory effects of histones, around which DNA are wrapped to form the nucleosomes and further the chromatin. The properties of chromatin can be altered either by nucleosome remodeling or by covalently modifying the N-terminal tails of histones. Here, we present an integrative approach that extends the yeast transcription factor network by sub-networks of histone-modifying proteins and addresses temporal aspects of potentially recruiting transcription factors and their behavior under different cellular conditions. We provide a thorough benchmark of sub-networks extracted form protein-protein and protein-DNA interaction data sets against genome-wide location data sets.