Computational Biology: First International Conference on Biology, Informatics, and Mathematics, JOBIM 2000 Montpellier, France, May 3-5, 2000 Selected Papers (Lecture Notes in Computer Science, 2066)

This book presents a selection of revised full papers accepted for presentation at the First International Conference on Biology, Informatics, and Mathematics, JOBIM 2000, held in Montpellier, France, in May 2000. The 13 papers included in the book were selected after two rounds of reviewing and revision from a total of 67 submissions. Among the topics addressed are algorithms, comparative genomics, evolution, phylogeny, databases, knowledge processing, genome anotation, graph theory, combinatorial mathematics, macromolecular structures, RNA and proteins, metabolic pathways and regulatory networks, and statistics and classification. Computational Biology Preface Organizing Committee Table of Contents Speeding Up the DIALIGN Multiple Alignment Program by Using the `Greedy Alignment of BIOlogical Sequences LIBrary' (GABIOS-LIB) Introduction The Consistency Problem for Partial Alignments Definitions and Notations Transitivity Frontiers and Consistency Bounds GABIOS-LIB The Incremental Algorithm EdgeAddition Further Reduction of Computing Time and Memory Time and Space Efficient Multiple Segment-by-Segment Alignment References GeMCore, a Knowledge Base Dedicated to Mapping Mammalian Genomes Introduction Requirements of Mapping Data Systems What Kind of System for Comparative Mapping? What Kind of Model for Comparative Mapping? GeMCore, a Knowledge Base Dedicated to Mapping Mammalian Genomes Conclusion References Appendix: Markers, Maps, and Recombination Optimal Agreement Supertrees Introduction Agreement Supertrees Four Standard Optimization Criteria Binary Character Weights Quartet Criteria Least Squares (OLS) Minimum Evolution (ME) Split Constrained Phylogenetic Optimization Optimal Agreement Supertree Algorithms Split Set Constraints Applications to Optimization Divide and Conquer Testing Stability Discussion Extension to Other Criteria Extension to Non-binary Trees Trees with No Agreement Supertree References Segmentation by Maximal Predictive Partitioning According to Composition Biases Prediction Prediction of Sequences Language of Predictors Predictive Partitioning of Sequences Predictive Partitions Number of Segments Algorithm Applications Composition Biases in Sequences Experiments References Can We Have Confidence in a Tree Representation? Introduction Criteria to Evaluate $X$-Trees Metric Criteria Topological Criteria Evaluating Average and Critical Values The Tree Model The Euclidean Model The Boolean Model The Protein Example References Bayesian Approach to DNA Segmentation into Regions with Different Average Nucleotide Composition Introduction Biological Motivation Current Algorithms for Compositional Segmentation Optimal Segmentation Probabilistic Formulation Choosing the Prior Segment Likelihood Dynamic Programming An Example Border Insertion Penalties Fluctuations in Local Composition Random Sequences Block Random Sequences Filtration of Boundaries Partition Function Dynamic Programming Filtration Strategy Partition Function Cutoff vs. Border Insertion Penalties An Example of the Large Scale Segmentation Discussion References Exact and Asymptotic Distribution of the Local Score of One i.i.d. Random Sequence Introduction New Asymptotic Distribution for the Local Score Exact Distribution of $M$ Properties of the Roots and Applications Local Score Exact Distribution for the Local Score Exact Distribution in Practice Alignment of Two Sequences with Shift Perspective and Conclusion References Phylogenetic Reconstruction Algorithms Based on Weighted 4-Trees Introduction A Criterion Based on $4$-Tree Partitioning Definitions and Notations A New Criterion Why Introduce a New Criterion? Weight Optimization and Path Optimization Principle Edge Bonus Computation Basic $O(n^4)$ Implementation of $WO$ Memory Space Required Optimizing the Propagations of Bonuses Experimental Comparison of {it WO}, {it PO} and {it QP} Protocol Methods Tested Results Conclusion References Computational Complexity of Word Counting Introduction Basic Tools Probabilistic Models Overlap and Correlation Sets Word Counting Complexity Correlation Automaton Various Examples 1-Partitions Approximate Matching PROSITE Expressions Conclusion References EUGÈNE: An Eukaryotic Gene Finder That Combines Several Sources of Evidence Methods Algorithm Scoring {sc EuG{{accent 18 e}}ne} in Action Evaluation References Tree Reconstruction via a Closure Operation on Partial Splits Introduction Preliminaries Split Closure Tree Reconstruction Using Split Closure References InterDB, a Prediction-Oriented Protein Interaction Database for C. elegans The Biological Problem: Protein-Protein Interactions The WISTdb Database Construction of InterDB from Current Databases Protein Interaction Prediction An ILP Approach An Association Rule Approach Conclusion References Application of Regulatory Sequence Analysis and Metabolic Network Analysis to the Interpretation of Gene Expression Data Introduction Gene Expression Data: A Study Case Visualization Regulatory Sequence Analysis Features of Cis-Regulatory Elements String-Based Approaches to Pattern Discovery in Regulatory Sequences Criteria for the Statistical Analysis of Words and Dyads Evaluation of String-Based Approaches with Known Regulons Application to Clusters Obtained from Microarray and Related Technologies Metabolic Network Analysis Representating Metabolic Pathways as Graphs Metabolic Pathway Discovery Metabolism and Gene Expression Applying Graph Analysis for a Functional Interpretation of Gene Expression Data Comparison of Extracted Pathways with Known Pathways Application of Pathway Analysis to the Study Case Conclusions Availability References Author Index

this Book Presents A Selection Of Revised Full Papers Accepted For Presentation At The First International Conference On Biology, Informatics, And Mathematics, Jobim 2000, Held In Montpellier, France, In May 2000.
the 13 Papers Included In The Book Were Selected After Two Rounds Of Reviewing And Revision From A Total Of 67 Submissions. Among The Topics Addressed Are Algorithms, Comparative Genomics, Evolution, Phylogeny, Databases, Knowledge Processing, Genome Anotation, Graph Theory, Combinatorial Mathematics, Macromolecular Structures, Rna And Proteins, Metabolic Pathways And Regulatory Networks, And Statistics And Classification.