The complexity of genome evolution has given birth to exciting challenges for computational biologists. A various range of algorithmic, statistical, mathem- ical techniques to elucidate the histories of molecules are developed each year and many are presented at the RECOMB satellite workshop on Comparative Genomics. It is a place where scientists working on all aspects of comparative genomics can share ideas on the development of tools and their application to relevant questions. This volume contains the papers presented at RECOMB-CG 2010, held on October 9–11 in Ottawa. The ?eld is still ?ourishing as seen from the papers presented this year: many developments enrich the combinatorics of genome rearrangements, while gene order phylogenies are becoming more and more - curate, thanks to a mixing of combinatorial and statistical principles, associated with rapid and thoughtful heuristics. Several papers tend to re?ne the models of genome evolution, and more and more genomic events can be modeled, from single nucleotide substitutions in whole genome alignments to large structural mutations or horizontal gene transfers.
Author(s): Robert Warren, David Sankoff (auth.), Eric Tannier (eds.)
Series: Lecture Notes in Computer Science 6398 : Lecture Notes in Bioinformatics
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2011
Language: English
Pages: 303
Tags: Computational Biology/Bioinformatics; Computer Appl. in Life Sciences; Bioinformatics; Symbolic and Algebraic Manipulation; Discrete Mathematics in Computer Science; Algorithm Analysis and Problem Complexity
Front Matter....Pages -
Genome Aliquoting Revisited....Pages 1-12
The Problem of Chromosome Reincorporation in DCJ Sorting and Halving....Pages 13-24
Advances on Genome Duplication Distances....Pages 25-38
Listing All Parsimonious Reversal Sequences: New Algorithms and Perspectives....Pages 39-49
Ultra-Perfect Sorting Scenarios....Pages 50-61
On Sorting Genomes with DCJ and Indels....Pages 62-73
The Zero Exemplar Distance Problem....Pages 74-82
Scaffold Filling under the Breakpoint Distance....Pages 83-92
An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers....Pages 93-108
Detecting Highways of Horizontal Gene Transfer....Pages 109-120
On Exploring Genome Rearrangement Phylogenetic Patterns....Pages 121-136
Fast and Accurate Phylogenetic Reconstruction from High-Resolution Whole-Genome Data and a Novel Robustness Estimator....Pages 137-148
A Simple Measure of the Dynamics of Segmented Genomes: An Application to Influenza....Pages 149-160
Novel Definition and Algorithm for Chaining Fragments with Proportional Overlaps....Pages 161-172
Assessing the Robustness of Complete Bacterial Genome Segmentations....Pages 173-187
An Algorithm to Solve the Motif Alignment Problem for Approximate Nested Tandem Repeats....Pages 188-197
Limited Lifespan of Fragile Regions in Mammalian Evolution....Pages 198-215
Mapping Association between Long-Range Cis -Regulatory Regions and Their Target Genes Using Comparative Genomics....Pages 216-227
A New Genomic Evolutionary Model for Rearrangements, Duplications, and Losses That Applies across Eukaryotes and Prokaryotes....Pages 228-239
A Simulation Tool for the Study of Symmetric Inversions in Bacterial Genomes....Pages 240-251
Consistency of Sequence-Based Gene Clusters....Pages 252-263
Efficient Computation of Approximate Gene Clusters Based on Reference Occurrences....Pages 264-277
The Complexity of the Gapped Consecutive-Ones Property Problem for Matrices of Bounded Maximum Degree....Pages 278-289
An Approximation Algorithm for Computing a Parsimonious First Speciation in the Gene Duplication Model....Pages 290-301
Back Matter....Pages -
