research-article

An efficient probabilistic population-based descent for the median genome problem

Authors:

Adrien Goeffon,

Macha Nikolski,

David J. ShermanAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 315 - 322

https://doi.org/10.1145/1389095.1389151

Published: 12 July 2008 Publication History

Abstract

We present a novel population-based local search algorithm for the median genome problem. The primary result of this article is that this probabilistic approach significantly improves the performance of ancestral genome reconstruction compared to existing methods, making it possible to tackle problems where the contemporary genomes may contain many hundreds of markers. Moreover, our method is not limited to triples of genomes, and thus solves the median genome problem in its generality. We show that in real application cases the computational results are highly robust, suggesting that we can interpret the computed median genomes as candidates carrying the semantics of ancestral architectures.

References

[1]

D. A. Bader, B. Moret, and M. Yan. A linear-time algorithm for computing inversion distances between signed permutations with an experimental study. Journal of Computational Biology, 8(5):483--491, 2001.]]

[2]

M. Bernt, D. Merkle, and M. Middendorf. Genome rearrangement based on reversals that preserve conserved intervals. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(3):275--288, 2006.]]

Digital Library

[3]

G. Bourque and P. A. Pevzner. Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Research, 12:26--36, 2002.]]

[4]

D. Bryant. The complexity of the breakpoint median problem. Technical Report CRM2579, Centre de Recherches Mathematiques, Universite de Montreal, 1998.]]

[5]

A. Caprara. Formulations and complexity of multiple sorting by reversals. In S. Istrail, P. Pevzner, and M. Waterman, editors, Proceedings of the Third Annual International Conference on Computational Molecular Biology (RECOMB-99), pages 84--93, Lyon, France, 1999. ACM Press.]]

Digital Library

[6]

A. Caprara. The Reversal Median Problem. INFORMS J. on Computing, 15(1):93--113, 2003.]]

Digital Library

[7]

A. Goeffon, J.-M. Richer, and J.-K. Hao. Progressive tree neighborhood applied to the maximum parsimony problem. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(1):136--145, 2008.]]

Digital Library

[8]

S. Hannenhalli and P. Pevzner. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pages 178--189. ACM Press, 1995.]]

Digital Library

[9]

H. H. Hoos and T. St¨utzle. Stochastic Local Search : Foundations & Applications (The Morgan Kaufmann Series in Artificial Intelligence). Morgan Kaufmann, 2004.]]

Digital Library

[10]

J. Meidanis and J. C. Setubal. Introduction to Computational Molecular Biology. PWS Publishing, 1997.]]

[11]

H. Muhlenbein and J. Zimmermann. Size of neighborhood more important than temperature for stochastic local search. In C. Cotta and J. I. van Hemert, editors, Proceedings of the 2000 Congress on Evolutionary Computation, volume 2, pages 1017--1024, 2000.]]

[12]

J. Nadeau and B. Taylor. Lengths of Chromosomal Segments Conserved since Divergence of Man and Mouse. Proceedings of the National Academy of Sciences of the United States of America, Part 1: Biological Sciences, 81(3):814--818, 1984.]]

[13]

J. M. Pasia, K. F. Doerner, R. F. Hartl, and M. Reimann. A population-based local search for solving a bi-objective vehicle routing problem. In C. Cotta and J. I. van Hemert, editors, EvoCOP, volume 4446 of Lecture Notes in Computer Science, pages 166--175. Springer, 2007.]]

Digital Library

[14]

I. Pe'er and R. Shamir. The median problems for breakpoints are NP-complete. Electronic Colloquium on Computational Complexity (ECCC), 5(071), 1998.]]

[15]

D. Sankoff and M. Blanchette. The median problem for breakpoints in comparative genomics. In COCOON '97: Proceedings of the Third Annual International Conference on Computing and Combinatorics, pages 251--264, London, UK, 1997. Springer-Verlag.]]

Digital Library

[16]

B. Selman, H. Levesque, and D. Mitchell. A new method for solving hard satisfiability problems. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 440--446, San Jose, CA, USA, 1992.]]

Digital Library

[17]

A. C. Siepel and B. M. E. Moret. Finding an optimal inversion median: Experimental results. In WABI '01: Proceedings of the First International Workshop on Algorithms in Bioinformatics, pages 189--203, London, UK, 2001. Springer-Verlag.]]

Digital Library

Cited By

Aganezov SAlekseyev M(2012)On pairwise distances and median score of three genomes under DCJBMC Bioinformatics10.1186/1471-2105-13-S19-S113:S19Online publication date: 19-Dec-2012
https://doi.org/10.1186/1471-2105-13-S19-S1
Vyahhi NGoëffon ANikolski MSherman DRothlauf F(2009)Swarming along the evolutionary branches sheds light on genome rearrangement scenariosProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569935(241-246)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569935
Souciet JDujon BGaillardin CJohnston MBaret PCliften PSherman DWeissenbach JWesthof EWincker PJubin CPoulain JBarbe VSegurens BArtiguenave FAnthouard VVacherie BVal MFulton RMinx PWilson RDurrens PJean GMarck CMartin TNikolski MRolland TSeret MCasaregola SDespons LFairhead CFischer GLafontaine ILeh VLemaire Mde Montigny JNeuveglise CThierry ABlanc-Lenfle IBleykasten CDiffels JFritsch EFrangeul LGoeffon AJauniaux NKachouri-Lafond RPayen CPotier SPribylova LOzanne CRichard GSacerdot CStraub MTalla E(2009)Comparative genomics of protoploid SaccharomycetaceaeGenome Research10.1101/gr.091546.10919:10(1696-1709)Online publication date: 12-Jun-2009
https://doi.org/10.1101/gr.091546.109
Show More Cited By

Index Terms

An efficient probabilistic population-based descent for the median genome problem
1. Applied computing
  1. Life and medical sciences
2. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

The Korea Brassica Genome Project: A glimpse of the Brassica genome based on comparative genome analysis with Arabidopsis: Conference Papers

A complete genome sequence provides unlimited information in the sequenced organism as well as in related taxa. According to the guidance of the Multinational Brassica Genome Project (MBGP), the Korea Brassica Genome Project (KBGP) is sequencing ...
Multichromosomal Genome Median and Halving Problems
WABI '08: Proceedings of the 8th international workshop on Algorithms in Bioinformatics

Genome median and halving problems aim at reconstructing ancestral genomes and the evolutionary events leading from the ancestor to extant species. The NP-hardness of the breakpoint distance and reversal distance median problems for unichromosomal ...
Genome halving problem revisited
FSTTCS'04: Proceedings of the 24th international conference on Foundations of Software Technology and Theoretical Computer Science

The Genome Halving Problem is motivated by the whole genome duplication events in molecular evolution that double the gene content of a genome and result in a perfect duplicated genome thatcontains two identical copies of each chromosome. The genome ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
101
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aganezov SAlekseyev M(2012)On pairwise distances and median score of three genomes under DCJBMC Bioinformatics10.1186/1471-2105-13-S19-S113:S19Online publication date: 19-Dec-2012
https://doi.org/10.1186/1471-2105-13-S19-S1
Vyahhi NGoëffon ANikolski MSherman DRothlauf F(2009)Swarming along the evolutionary branches sheds light on genome rearrangement scenariosProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1569935(241-246)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1569935
Souciet JDujon BGaillardin CJohnston MBaret PCliften PSherman DWeissenbach JWesthof EWincker PJubin CPoulain JBarbe VSegurens BArtiguenave FAnthouard VVacherie BVal MFulton RMinx PWilson RDurrens PJean GMarck CMartin TNikolski MRolland TSeret MCasaregola SDespons LFairhead CFischer GLafontaine ILeh VLemaire Mde Montigny JNeuveglise CThierry ABlanc-Lenfle IBleykasten CDiffels JFritsch EFrangeul LGoeffon AJauniaux NKachouri-Lafond RPayen CPotier SPribylova LOzanne CRichard GSacerdot CStraub MTalla E(2009)Comparative genomics of protoploid SaccharomycetaceaeGenome Research10.1101/gr.091546.10919:10(1696-1709)Online publication date: 12-Jun-2009
https://doi.org/10.1101/gr.091546.109
Jean GSherman DNikolski M(2009)Mining the Semantics of Genome Super-Blocks to Infer Ancestral ArchitecturesJournal of Computational Biology10.1089/cmb.2008.004616:9(1267-1284)Online publication date: Sep-2009
https://doi.org/10.1089/cmb.2008.0046

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten