Z. Adam, M. Turmel, C. Lemieux, and D. Sankoff, Common Intervals and Symmetric Difference in a Model-Free Phylogenomics, with an Application to Streptophyte Evolution, Journal of Computational Biology, vol.14, issue.4, pp.436-445, 2007.
DOI : 10.1089/cmb.2007.A005

M. Alekseyev and P. Pevzner, Colored de Bruijn Graphs and the Genome Halving Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.4, issue.1, pp.98-107, 2007.
DOI : 10.1109/TCBB.2007.1002

F. Alizadeh, R. Karp, D. Weisser, and G. Zweig, Physical Mapping of Chromosomes Using Unique Probes, Journal of Computational Biology, vol.2, issue.2, pp.159-184, 1995.
DOI : 10.1089/cmb.1995.2.159

M. Beal, A. Bergeron, S. Corteel, and M. Raffinot, An algorithmic view of gene teams, Theoretical Computer Science, vol.320, issue.2-3, pp.395-418, 2004.
DOI : 10.1016/j.tcs.2004.02.036

URL : https://hal.archives-ouvertes.fr/hal-00619206

M. Belcaid, A. Bergeron, A. Chateau, C. Chauve, Y. Gingras et al., EXPLORING GENOME REARRANGEMENTS USING VIRTUAL HYBRIDIZATION, Proceedings of the 5th Asia-Pacific Bioinformatics Conference, pp.205-214, 2007.
DOI : 10.1142/9781860947995_0023

URL : https://hal.archives-ouvertes.fr/lirmm-00203873

M. J. Benton and P. C. Donoghue, Paleontological Evidence to Date the Tree of Life, Molecular Biology and Evolution, vol.24, issue.1, pp.26-53, 2007.
DOI : 10.1093/molbev/msl150

S. Bérard, A. Bergeron, C. Chauve, and C. Paul, Perfect Sorting by Reversals Is Not Always Difficult, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.4, issue.1, pp.4-16, 2007.
DOI : 10.1109/TCBB.2007.1011

A. Bergeron, M. Blanchette, A. Chateau, and C. Chauve, Reconstructing Ancestral Gene Orders Using Conserved Intervals, Algorithms in Bioinformatics Lecture Notes in Computer Science, vol.3240, pp.14-25, 2004.
DOI : 10.1007/978-3-540-30219-3_2

A. Bergeron, C. Chauve, and Y. Gingras, Bioinformatics Algorithms: Techniques and Applications (A. Zelikovsky and I. Mandoiu, editors), chapter INRIA Formal models of gene clusters, Wiley Series on Bioinformatics: Computational Techniques and Engineering. Wiley Interscience

A. Bhutkar, W. Gelbart, and T. Smith, Inferring genome-scale rearrangement phylogeny and ancestral gene order: a Drosophila case study, Genome Biology, vol.8, issue.11, p.236, 2007.
DOI : 10.1186/gb-2007-8-11-r236

K. Booth and G. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, vol.13, issue.3, pp.335-379, 1976.
DOI : 10.1016/S0022-0000(76)80045-1

G. Bourque and P. Pevzner, Genome-scale evolution: reconstructing gene orders in the ancestral species, Genome Research, vol.12, pp.26-36, 2002.

G. Bourque, P. Pevzner, and G. Tesler, Reconstructing the Genomic Architecture of Ancestral Mammals: Lessons From Human, Mouse, and Rat Genomes, Genome Research, vol.14, issue.4
DOI : 10.1101/gr.1975204

G. Bourque, G. Tesler, and P. Pevzner, The convergence of cytogenetics and rearrangement-based models for ancestral genome reconstruction, Genome Research, vol.16, issue.3, pp.311-313, 2006.
DOI : 10.1101/gr.4631806

G. Bourque, E. Zdobnov, P. Bork, P. Pevzner, and G. Tesler, Comparative architectures of mammalian and chicken genomes reveal highly variable rates of genomic rearrangements across different lineages, Genome Research, vol.15, issue.1, pp.98-110, 2005.
DOI : 10.1101/gr.3002305

A. Caprara, F. Malucelli, and D. Pretolani, On bandwidth-2 graphs, Discrete Applied Mathematics, vol.117, issue.1-3, pp.1-13, 2002.
DOI : 10.1016/S0166-218X(01)00196-2

T. Christof, M. Jnger, J. Kececioglu, P. Mutzel, and G. Reinelt, A Branch-and-Cut Approach to Physical Mapping of Chromosomes by Unique End-Probes, Journal of Computational Biology, vol.4, issue.4, pp.433-447, 1997.
DOI : 10.1089/cmb.1997.4.433

A. Darling, B. Mau, F. Blattner, and N. Perna, Mauve: Multiple Alignment of Conserved Genomic Sequence With Rearrangements, Genome Research, vol.14, issue.7, pp.1394-1403, 2004.
DOI : 10.1101/gr.2289704

Y. V. De-peer, Computational approaches to unveiling ancient genome duplications, Nature Reviews Genetics, vol.19, issue.10, pp.752-763, 2004.
DOI : 10.1093/molbev/msh114

M. Dom, J. Guo, and R. Niedermeier, Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems, Theory and Applications of Models of Computation, 4th International Conference Proceedings, volume 4484 of Lecture Notes in Computer Science, pp.680-691, 2007.
DOI : 10.1007/978-3-540-72504-6_62

M. Dom, J. Guo, R. Niedermeier, and S. Wernicke, Minimum Membership Set Covering and the Consecutive Ones Property, Algorithm Theory -SWAT 2006, pp.339-350, 2006.
DOI : 10.1007/11785293_32

J. Earnest-deyoung, E. Lerat, and B. Moret, Reversing Gene Erosion ??? Reconstructing Ancestral Bacterial Genomes from Gene-Content and Order Data
DOI : 10.1007/978-3-540-30219-3_1

URL : https://hal.archives-ouvertes.fr/hal-00427561

N. El-mabrouk and D. Sankoff, The Reconstruction of Doubled Genomes, SIAM Journal on Computing, vol.32, issue.3, pp.754-792, 2003.
DOI : 10.1137/S0097539700377177

T. Faraut, Addressing chromosome evolution in the whole-genome sequence era, Chromosome Research, vol.298, issue.1, pp.5-16, 2008.
DOI : 10.1007/s10577-007-1208-0

L. Froenicke, M. G. Caldés, A. Graphodatsky, S. Mueller, L. Lyons et al., Are molecular cytogenetics and bioinformatics suggesting diverging models of ancestral mammalian genomes?, Genome Research, vol.16, issue.3, pp.306-310, 2006.
DOI : 10.1101/gr.3955206

L. Froenicke, J. Wienberg, G. Stone, L. Adams, and R. Stanyon, Towards the delineation of the ancestral eutherian genome organization: comparative genome maps of human and the African elephant (Loxodonta africana) generated by chromosome painting, Proceedings of the Royal Society B: Biological Sciences, vol.270, issue.1522, pp.1331-1340, 2003.
DOI : 10.1098/rspb.2003.2383

P. Goldberg, M. Golumbic, H. Kaplan, and R. Shamir, Four Strikes Against Physical Mapping of DNA, Journal of Computational Biology, vol.2, issue.1, pp.139-152, 1995.
DOI : 10.1089/cmb.1995.2.139

M. Habib, R. Mcconnell, C. Paul, and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, vol.234, issue.1-2, pp.59-84, 2000.
DOI : 10.1016/S0304-3975(97)00241-7

M. Hajiaghayi and Y. Ganjali, A note on the Consecutive Ones Submatrix problem, Information Processing Letters, vol.83, issue.3, pp.163-166, 2002.
DOI : 10.1016/S0020-0190(01)00325-8

D. Karolchik, R. Kuhn, R. Baertsch, G. Barber, H. Clawson et al., The UCSC Genome Browser Database: 2008 update, Nucleic Acids Research, vol.36, issue.Database, pp.773-779, 2007.
DOI : 10.1093/nar/gkm966

C. Kemkemer, M. Kohn, H. Kehrer-sawatzki, P. Minich, J. Högel et al., Reconstruction of the ancestral ferungulate karyotype by electronic chromosome painting (E-painting), Chromosome Research, vol.215, issue.8, pp.899-907, 2006.
DOI : 10.1007/s10577-006-1097-7

K. Lindblad-toh, C. Wade, T. Mikkelsen, E. Karlsson, D. Jaffe et al., Genome sequence, comparative analysis and haplotype structure of the domestic dog, Nature, vol.426, issue.7069, pp.803-819, 2005.
DOI : 10.1038/nature04338

N. Luc, J. Risler, A. Bergeron, and M. Raffinot, Gene teams: a new formalization of gene clusters for comparative genomics, Computational Biology and Chemistry, vol.27, issue.1, pp.59-67, 2003.
DOI : 10.1016/S1476-9271(02)00097-X

J. Ma, L. Zhang, B. Suh, B. Rany, R. Burhans et al., Reconstructing contiguous regions of an ancestral genome, Genome Research, vol.16, issue.12, pp.1557-1565, 2006.
DOI : 10.1101/gr.5383506

R. Mcconnell, A certifying algorithm for the consecutive-ones property

J. Meidanis, O. Porto, and G. Telles, On the consecutive ones property, Discrete Applied Mathematics, vol.88, issue.1-3, pp.325-354, 1998.
DOI : 10.1016/S0166-218X(98)00078-X

T. Mikkelsen, M. Wakefield, B. Aken, C. Amemiya, J. Chang et al., Genome of the marsupial Monodelphis domestica reveals innovation in non-coding sequences, Nature, vol.22, issue.7141, pp.167-177, 2007.
DOI : 10.1038/nature05805

M. Muffato and H. R. Crollius, Paleogenomics in vertebrates, or the recovery of lost genomes from the mist of time, BioEssays, vol.270, issue.2, pp.122-134, 2008.
DOI : 10.1002/bies.20707

W. Murphy, D. Larkin, A. E. Van-der-wind, G. Bourque, G. Tesler et al., Dynamics of Mammalian Chromosome Evolution Inferred from Multispecies Comparative Maps, Science, vol.309, issue.5734, pp.613-617, 2005.
DOI : 10.1126/science.1111387

Y. Nakatani, H. Takeda, and S. Morishita, Reconstruction of the vertebrate ancestral genome reveals dynamic genome reorganization in early vertebrates, Genome Research, vol.17, issue.9, pp.1254-1265, 2007.
DOI : 10.1101/gr.6316407

L. Parida, Using PQ Structures for Genomic Rearrangement Phylogeny, Journal of Computational Biology, vol.13, issue.10, pp.1685-1700, 2006.
DOI : 10.1089/cmb.2006.13.1685

S. Pasek, A. Bergeron, J. Risler, A. Louis, E. Ollivier et al., Identification of genomic features using microsyntenies of domains: Domain teams, Genome Research, vol.15, issue.6, pp.867-874, 2005.
DOI : 10.1101/gr.3638405

V. L. Rascol, P. Pontarotti, and A. Levasseur, Ancestral animal genomes reconstruction, Current Opinion in Immunology, vol.19, issue.5, pp.542-546, 2007.
DOI : 10.1016/j.coi.2007.06.009

R. Genome and S. Consortium, Genome sequence of the Brown Norway rat yields insights into mammalian evolution, Nature, vol.428, issue.6982, pp.493-521, 2004.
DOI : 10.1038/nature02426

F. Richard, M. Lombard, and B. Dutrillaux, Reconstruction of the ancestral karyotype of eutherian mammals, Chromosome Research, vol.11, issue.6, pp.605-618, 2003.
DOI : 10.1023/A:1024957002755

M. Rocchi, N. Archidiacono, and R. Stanyon, Ancestral genomes reconstruction: An integrated, multi-disciplinary approach is needed, Genome Research, vol.16, issue.12, pp.1441-1444, 2006.
DOI : 10.1101/gr.5687906

D. Sankoff, C. Zheng, and Q. Zhu, Polyploids, genome halving and phylogeny, Bioinformatics, vol.23, issue.13, pp.433-439, 2007.
DOI : 10.1093/bioinformatics/btm169

A. Sinha and J. Meller, Cinteny: flexible analysis and visualization of synteny and genome rearrangements in multiple organisms, BMC Bioinformatics, vol.8, issue.1, 2007.
DOI : 10.1186/1471-2105-8-82

M. Svartman, G. Stone, J. Page, and R. Stanyon, A chromosome painting test of the basal Eutherian karyotype, Chromosome Research, vol.12, issue.1, pp.45-53, 2004.
DOI : 10.1023/B:CHRO.0000009294.18760.e4

M. Svartman, G. Stone, and R. Stanyon, The Ancestral Eutherian Karyotype Is Present in Xenarthra, PLoS Genetics, vol.11, issue.7, p.109, 2006.
DOI : 0140-6736(1971)011[0971:ARBTFH]2.0.CO;2

F. Swidan, E. Rocha, M. Shmoish, and R. Pinter, An Integrative Method for Accurate Comparative Genome Mapping, PLoS Computational Biology, vol.34, issue.8, p.75, 2006.
DOI : 10.1371/journal.pcbi.0020075.st005

J. Tang and L. Zhang, The consecutive ones submatrix problem for sparse matrices, Algorithmica, vol.48, pp.287-299, 2007.

J. Wienberg, The evolution of eutherian chromosomes, Current Opinion in Genetics & Development, vol.14, issue.6, pp.657-666, 2004.
DOI : 10.1016/j.gde.2004.10.001

]. R. Wittler, ROCI; -reconstruction of conserved intervals

F. Yang, E. Alkalaeva, P. Perelman, A. Pardini, W. Harrison et al., Reciprocal chromsome painting among human, aardvark, and elephant (superorder afrotheria) reveals the likely eutherian ancestral karyotype, Proceedings of the National Academy of Science of the United States of America, pp.1062-1066, 2003.