Comparative Genomics

The complexity of genome evolution poses many exciting challenges to devel- ers of mathematical models and algorithms, who have recourse to a spectrum of algorithmic,statisticalandmathematicaltechniques,rangingfromexact,heur- tic, ?xed-parameter and approximation algorithms for problems based on par- mony models to Monte Carlo Markov Chain algorithms for Bayesian analysis of problems based on probabilistic models. The annual RECOMB Satellite Workshop on Comparative Genomics (RECOMB ComparativeGenomics)is aforumonallaspects andcomponents of this ?eld,rangingfromnew quantitativediscoveriesabout genomestructureand process to theorems on the complexity of computational problems inspired by genome comparison. The informal steering committee for this meeting consists of David Sanko?, Jens Lagergren and Aoife McLysaght. Thisvolumecontainsthepaperspresentedatthe3rdRECOMBComparative Genomicsmeeting,whichwasheldinDublin,Ireland,onSeptember18 20,2005. The ?rst two meetings of this series were held in Minneapolis, USA (2003) and Bertinoro, Italy (2004). This year, 21 papers were submitted, of which the Program Committee - lected 14 for presentation at the meeting and inclusion in this proceedings.Each submission was refereed by at least three members of the Program Committee. Aftercompletionofthereferees reports,anextensiveWeb-baseddiscussiontook placeformakingdecisions.TheRECOMBComparativeGenomics2005Program Committee consisted of the following 27 members: Vineet Bafna, Anne Be- eron, Mathieu Blanchette, Avril Coghlan, Dannie Durand, Nadia El-Mabrouk, Niklas Eriksen, Aaron Halpern, Rose Hoberman, Daniel Huson, Jens Lagergren, Giuseppe Lancia, Emmanuelle Lerat, Aoife McLysaght, Istvan Miklos, Bernard Moret, PavelPevzner, Ben Raphael, Marie-FranceSagot, David Sanko?, Cathal Seoighe, Beth Shapiro, Igor Sharakhov, Mike Steel, Jens Stoye, Glenn Tesler and Louxin Zhan. We would like to thank the ProgramCommittee members for their dedication and hard work.

Texte du rabat

Cathal Seoighe, Beth Shapiro, Igor Sharakhov, Mike Steel, Jens Stoye, Glenn Tesler and Louxin Zhan. We would like to thank the ProgramCommittee members for their dedication and hard work.

Contenu
Lower Bounds for Maximum Parsimony with Gene Order Data.- Genes Order and Phylogenetic Reconstruction: Application to ?-Proteobacteria.- Maximizing Synteny Blocks to Identify Ancestral Homologs.- An Expectation-Maximization Algorithm for Analysis of Evolution of Exon-Intron Structure of Eukaryotic Genes.- Likely Scenarios of Intron Evolution.- OMA, A Comprehensive, Automated Project for the Identification of Orthologs from Complete Genome Data: Introduction and First Achievements.- The Incompatible Desiderata of Gene Cluster Properties.- The String Barcoding Problem is NP-Hard.- A Partial Solution to the C-Value Paradox.- Individual Gene Cluster Statistics in Noisy Maps.- Power Boosts for Cluster Tests.- Reversals of Fortune.- Very Low Power to Detect Asymmetric Divergence of Duplicated Genes.- A Framework for Orthology Assignment from Gene Rearrangement Data.