R. Agarwala and D. Fernandez-baca, A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed, SIAM Journal on Computing, vol.23, issue.6, pp.1216-1224, 1994.

D. Aldous, Probability distributions on cladograms, Random discrete structures, pp.1-18, 1996.

C. Ané, Detecting phylogenetic breakpoints and discordance from genome-wide alignments for species tree reconstruction, Genome biology and evolution, vol.3, pp.246-258, 2011.

M. Anisimova, R. Nielsen, and Z. Yang, Effect of recombination on the accuracy of the likelihood method for detecting positive selection at amino acid sites, Genetics, vol.164, issue.3, pp.1229-1236, 2003.

M. Arenas and D. Posada, Coalescent simulation of intracodon recombination, Genetics, vol.184, issue.2, pp.429-437, 2010.

M. Arenas and D. Posada, The effect of recombination on the reconstruction of ancestral sequences, Genetics, vol.184, issue.4, pp.1133-1139, 2010.

E. W. Bloomquist, K. S. Dorman, and M. A. Suchard, StepBrothers: inferring partially shared ancestries among recombinant viral sequences, Biostatistics, vol.10, pp.106-120, 2008.

M. F. Boni, D. Posada, and M. W. Feldman, An exact nonparametric method for inferring mosaic structure in sequence triplets, Genetics, vol.176, issue.2, pp.1035-1047, 2007.

B. Boussau, L. Guéguen, and M. Gouy, A mixture model and a hidden markov model to simultaneously detect recombination breakpoints and reconstruct phylogenies, Evolutionary Bioinformatics, vol.5, p.2242, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00428395

P. Buneman, The Recovery of Trees from Measures of Dissimilarity, Mathematics the the Archeological and Historical Sciences, pp.387-395, 1971.

R. A. Cartwright, DNA assembly with gaps (dawg): simulating sequence evolution, Bioinformatics, vol.21, issue.Suppl_3, pp.31-38, 2005.

R. G. Downey, M. R. Fellows, J. Y. Dutheil, G. Ganapathy, A. Hobolth et al., Ancestral population genomics: the coalescent hidden markov model approach, Springer Science & Business Media, vol.183, pp.259-274, 2009.

G. J. Etherington, J. Dicks, and I. N. Roberts, Recombination analysis tool (rat): a program for the high-throughput detection of recombination, Bioinformatics, vol.21, issue.3, pp.278-281, 2004.

J. Felsenstein, Cases in which parsimony or compatibility methods will be positively misleading, Systematic zoology, vol.27, issue.4, pp.401-410, 1978.

D. Fernández-baca and J. Lagergren, A polynomial-time algorithm for near-perfect phylogeny, SIAM Journal on Computing, vol.32, issue.5, pp.1115-1127, 2003.

J. Flum and M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science, An EATCS Series, 2006.

M. J. Gibbs, J. S. Armstrong, and A. J. Gibbs, Sister-scanning: a monte carlo procedure for assessing signals in recombinant sequences, Bioinformatics, vol.16, issue.7, pp.573-582, 2000.

N. C. Grassly and E. C. Holmes, A likelihood method for the detection of selection and recombination using nucleotide sequences, Molecular Biology and Evolution, vol.14, issue.3, pp.239-247, 1997.

P. Hansen, A. Hertz, and J. Kuplinsky, Bounded vertex colorings of graphs, Discrete Mathematics, vol.111, issue.1-3, pp.305-312, 1993.

E. Harding, The probabilities of rooted tree-shapes generated by random bifurcation, Advances in Applied Probability, vol.3, issue.1, pp.44-77, 1971.

J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, Journal of Molecular Evolution, vol.36, issue.4, pp.396-405, 1993.

A. Hobolth, O. F. Christensen, T. Mailund, and M. H. Schierup, Genomic relationships and speciation times of human, chimpanzee, and gorilla inferred from a coalescent hidden markov model, PLoS genetics, vol.3, issue.2, p.7, 2007.

E. C. Holmes, M. Worobey, and A. Rambaut, Phylogenetic evidence for recombination in dengue virus, Molecular biology and evolution, vol.16, issue.3, pp.405-409, 1999.

R. R. Hudson and N. L. Kaplan, Statistical properties of the number of recombination events in the history of a sample of DNA sequences, Genetics, vol.111, issue.1, pp.147-164, 1985.

D. Husmeier and G. Mcguire, Detecting recombination in 4-taxa DNA sequence alignments with bayesian hidden markov models and markov chain monte carlo, Molecular Biology and Evolution, vol.20, issue.3, pp.315-337, 2003.

D. H. Huson, R. Rupp, and C. Scornavacca, Phylogenetic networks: concepts, algorithms and applications, 2010.

S. Kannan and T. Warnow, A fast algorithm for the computation and enumeration of perfect phylogenies, SIAM Journal on Computing, vol.26, issue.6, pp.1749-1763, 1997.

J. F. Kingman, On the genealogy of large populations, Journal of applied probability, vol.19, pp.27-43, 1982.

K. Pond, S. Poon, A. Zarate, S. Smith, D. Little et al., Estimating selection pressures on hiv-1 using phylogenetic likelihood models, Statistics in medicine, vol.27, issue.23, pp.4779-4789, 2008.

K. Pond, S. L. Posada, D. Gravenor, M. B. Woelk, C. H. Frost et al., Automated phylogenetic detection of recombination using a genetic algorithm, Molecular biology and evolution, vol.23, issue.10, pp.1891-1901, 2006.

K. Pond, S. L. Posada, D. Gravenor, M. B. Woelk, C. H. Frost et al., Gard: a genetic algorithm for recombination detection, Bioinformatics, vol.22, issue.24, pp.3096-3098, 2006.

A. M. Kozlov, A. J. Aberer, and A. Stamatakis, Examl version 3: a tool for phylogenomic analyses on supercomputers, Bioinformatics, vol.31, issue.15, pp.2577-2579, 2015.

H. M. Lam, O. Ratmann, and M. F. Boni, Improved algorithmic complexity for the 3seq recombination detection algorithm, Molecular biology and evolution, vol.35, issue.1, pp.247-251, 2017.

P. Lemey and D. Posada, Introduction to recombination detection, The phylogenetic handbook: a practical approach to phylogenetic analysis and hypothesis testing, vol.15, pp.493-518, 2009.

S. Linz, K. S. John, and C. Semple, Optimizing tree and character compatibility across several phylogenetic trees, Theoretical Computer Science, vol.513, pp.129-136, 2013.

K. S. Lole, R. C. Bollinger, R. S. Paranjape, D. Gadkari, S. S. Kulkarni et al., Full-length human immunodeficiency virus type 1 genomes from subtype c-infected seroconverters in india, with evidence of intersubtype recombination, Journal of virology, vol.73, issue.1, pp.152-160, 1999.

D. P. Martin, P. Lemey, M. Lott, V. Moulton, D. Posada et al., Rdp3: a flexible and fast computer program for analyzing recombination, Bioinformatics, vol.26, pp.2462-2463, 2010.

D. P. Martin, P. Lemey, and D. Posada, Analysing recombination in nucleotide sequences, Molecular Ecology Resources, vol.11, issue.6, pp.943-955, 2011.

D. P. Martin, B. Murrell, A. Khoosal, and B. Muhire, Detecting and analyzing genetic recombination using rdp4, Bioinformatics, pp.433-460, 2017.

J. Maydt and T. Lengauer, Recco: recombination analysis using cost optimization, Bioinformatics, vol.22, issue.9, pp.1064-1071, 2006.

G. Mcguire, F. Wright, and M. J. Prentice, A graphical method for detecting recombination in phylogenetic data sets, Molecular Biology and Evolution, vol.14, issue.11, pp.1125-1131, 1997.

V. N. Minin, K. S. Dorman, F. Fang, and M. A. Suchard, Dual multiple change-point model leads to more accurate recombination detection, Bioinformatics, vol.21, issue.13, pp.3034-3042, 2005.

L. De-oliveira-martins, E. Leal, and H. Kishino, Phylogenetic detection of recombination with a bayesian prior on the distance between trees, PLoS One, vol.3, issue.7, p.2651, 2008.

M. Padidam, S. Sawyer, and C. M. Fauquet, Possible emergence of new geminiviruses by frequent recombination, Virology, vol.265, issue.2, pp.218-225, 1999.

D. Posada and K. A. Crandall, Evaluation of methods for detecting recombination from DNA sequences: computer simulations, Proceedings of the National Academy of Sciences, vol.98, issue.24, pp.13757-13762, 2001.

D. Posada and K. A. Crandall, The effect of recombination on the accuracy of phylogeny estimation, Journal of molecular evolution, vol.54, issue.3, pp.396-402, 2002.

D. Ruths and L. Nakhleh, RECOMP: A parsimony-based method for detecting recombination, Proceedings Of The 4th Asia-Pacific Bioinformatics Conference, pp.59-68, 2006.

M. Salminen and D. P. Martin, Detecting and characterizing individual recombination events, The phylogenetic handbook: a practical approach to phylogenetic analysis and hypothesis testing, vol.16, pp.519-548, 2009.

M. O. Salminen, J. K. Carr, D. S. Burke, and F. E. Mccutchan, Identification of breakpoints in intergenotypic recombinants of hiv type 1 by bootscanning, AIDS research and human retroviruses, vol.11, issue.11, pp.1423-1425, 1995.

S. Sawyer, Statistical tests for detecting gene conversion, Molecular biology and evolution, vol.6, issue.5, pp.526-538, 1989.

K. Scheffler, D. P. Martin, and C. Seoighe, Robust inference of positive selection from recombining coding sequences, Bioinformatics, vol.22, issue.20, pp.2493-2499, 2006.

M. H. Schierup and J. Hein, Consequences of recombination on traditional phylogenetic analysis, Genetics, vol.156, issue.2, pp.879-891, 2000.

A. C. Siepel, A. L. Halpern, C. Macken, and B. T. Korber, A computer program designed to screen rapidly for hiv type 1 intersubtype recombinant sequences, AIDS research and human retroviruses, vol.11, issue.11, pp.1413-1416, 1995.

J. M. Smith, Analyzing the mosaic structure of genes, Journal of molecular evolution, vol.34, issue.2, pp.126-129, 1992.

H. Song, E. E. Giorgi, V. V. Ganusov, F. Cai, G. Athreya et al., Tracking hiv-1 recombination to resolve its contribution to hiv-1 evolution in natural infection, Nature communications, vol.9, issue.1, p.1928, 2018.

S. Sridhar, K. Dhamdhere, G. Blelloch, E. Halperin, R. Ravi et al., Algorithms for efficient near-perfect phylogenetic tree reconstruction in theory and practice, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.4, issue.4, pp.561-571, 2007.

M. Tsimpidis, G. Bachoumis, K. Mimouli, Z. Kyriakopoulou, D. L. Robertson et al., T-recs: rapid and large-scale detection of recombination events among different evolutionary lineages of viral genomes, BMC bioinformatics, vol.18, issue.1, p.13, 2017.

A. Webb, J. M. Hancock, and C. C. Holmes, Phylogenetic inference under recombination using bayesian stochastic topology selection, Bioinformatics, vol.25, issue.2, pp.197-203, 2008.

G. F. Weiller, Phylogenetic profiles: a graphical method for detecting genetic recombinations in homologous sequences, Molecular Biology and Evolution, vol.15, issue.3, pp.326-335, 1998.

B. Xu and Z. Yang, Challenges in species tree estimation under the multispecies coalescent model, Genetics, vol.204, issue.4, pp.1353-1368, 2016.

, So the alignment consists of two blocks, where the first has length location and the second has length (400 ? location), vol.100

, As indicated earlier: for each t, b?, location parameter combination we take 20 replicates, and each replicate selects new trees and alignments

?. For and . {5, CutAl solves each replicate to optimality (for all four optimization models combined) in time ranging from 3 seconds to 11 seconds. For t = 20 the running time varies between 11s and 43s, and within this range increases with branch length. For t = 50 the running time varies between 57s and 425s, again increasing inside this range with branch length

, See Table 1 for the results. In each row, the smallest average (ranging across the four optimization models) is shown in bold

, Protocol specific to multiple-block experiment and summary of running times 1. We select k ? {3, 4, 5, p.6

, Unlike the 2-block experiment, where every replicate uses new trees and new alignments, in this case every replicate also randomly selects new breakpoint locations

, Breakpoint locations are sampled uniformly at random, subject to the following rules: the length of each block is a multiple of 50, p.50

, This is due to technicalities associated with completely uninformative blocks, discussed earlier. Specifically, with these parameter combinations the chance of observing an alignment where all blocks are informative is extremely low

, Running times are of a similar magnitude, and follow a similar pattern, to the 2-block experiment. The number of taxa, and then to a lesser extent the branch lengths, and then to a lesser extent the number of blocks

, See Table 2 for the results. In each row, the smallest average (ranging across the four optimization models) is shown in bold