{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T04:31:40Z","timestamp":1775017900817,"version":"3.50.1"},"reference-count":264,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Bioinformatics regularly poses new challenges to algorithm engineers and theoretical computer scientists. This work surveys recent developments of parameterized algorithms and complexity for important NP-hard problems in bioinformatics. We cover sequence assembly and analysis, genome comparison and completion, and haplotyping and phylogenetics. Aside from reporting the state of the art, we give challenges and open problems for each topic.<\/jats:p>","DOI":"10.3390\/a12120256","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T10:50:45Z","timestamp":1575283845000},"page":"256","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Parameterized Algorithms in Bioinformatics: An Overview"],"prefix":"10.3390","volume":"12","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[{"name":"Centre national de la recherche scientifique (CNRS), Universit\u00e9 Paris-Est Marne-la-Vall\u00e9e, 77454 Marne-la-Vall\u00e9e, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9653-3690","authenticated-orcid":false,"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[{"name":"Centre national de la recherche scientifique (CNRS), Universit\u00e9 Paris-Est Marne-la-Vall\u00e9e, 77454 Marne-la-Vall\u00e9e, France"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_3","unstructured":"\u00c1vila, L.F., Garc\u00eda, A., Serna, M.J., and Thilikos, D.M. Parameterized Problems in Bioinformatics, unpublished manuscript."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1093\/comjnl\/bxm035","article-title":"Parameterized Complexity and Biopolymer Sequence Comparison","volume":"51","author":"Cai","year":"2008","journal-title":"Comput. J."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"H\u00fcffner, F., Komusiewicz, C., Niedermeier, R., and Wernicke, S. (2017). Parameterized Algorithmics for Finding Exact\nSolutions of NP-Hard Biological Problems. Bioinformatics: Volume II: Structure, Function, and Applications, Springer.","DOI":"10.1007\/978-1-4939-6613-4_20"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1093\/comjnl\/bxm049","article-title":"Fixed-Parameter Algorithms in Phylogenetics","volume":"51","author":"Gramm","year":"2007","journal-title":"Comput. J."},{"key":"ref_7","unstructured":"Griffiths, A.J., Gelbart, W.M., Miller, J.H., and Lewontin, R.C. (1999). Chromosomal Rearrangements. Modern Genetic Analysis, W.H.Freeman. Chapter 8."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Fertin, G., Labarre, A., Rusu, I., Tannier, E., and Vialette, S. (2009). Combinatorics of Genome Rearrangements, MIT Press.","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"Efficient sorting of genomic permutations by translocation, inversion and block interchange","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bergeron, A., Mixtacki, J., and Stoye, J. (2006). A unifying view of genome rearrangements. International Workshop on Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/11851561_16"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Chauve, C., Fertin, G., Rizzi, R., and Vialette, S. (2006). Genomes containing duplicates are hard to compare. International Conference on Computational Science, Springer.","DOI":"10.1007\/11758525_105"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1093\/bioinformatics\/btq674","article-title":"Algorithms for sorting unsigned linear genomes by the DCJ operations","volume":"27","author":"Jiang","year":"2010","journal-title":"Bioinformatics"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1186\/s13015-017-0107-y","article-title":"Algorithms for computing the double cut and join distance on both gene order and intergenic sizes","volume":"12","author":"Fertin","year":"2017","journal-title":"Algorithms Mol. Biol."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"B\u00e9rard, S., Chateau, A., Chauve, C., Paul, C., and Tannier, E. (2008). Perfect DCJ rearrangement. RECOMB International Workshop on Comparative Genomics, Springer.","DOI":"10.1007\/978-3-540-87989-3_12"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-5193(82)90384-8","article-title":"The chromosome inversion problem","volume":"99","author":"Watterson","year":"1982","journal-title":"J. Theor. Biol."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","article-title":"Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals","volume":"46","author":"Hannenhalli","year":"1999","journal-title":"J. ACM"},{"key":"ref_17","unstructured":"Christie, D.A. (1998). Genome Rearrangement Problems. [Ph.D. Thesis, University of Glasgow]."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1109\/TCBB.2005.48","article-title":"Assignment of Orthologous Genes via Genome Rearrangement","volume":"2","author":"Chen","year":"2005","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S0895480103433550","article-title":"Reversals and transpositions over finite alphabets","volume":"19","author":"Radcliffe","year":"2006","journal-title":"SIAM J. Discret. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01188586","article-title":"Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement","volume":"13","author":"Kececioglu","year":"1995","journal-title":"Algorithmica"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bulteau, L., Fertin, G., and Komusiewicz, C. (2014). Reversal distances for strings with few blocks or small alphabets. Symposium on Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/978-3-319-07566-2_6"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.ipl.2007.10.012","article-title":"A more efficient algorithm for perfect sorting by reversals","volume":"106","author":"Chauve","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Dias, Z., and Meidanis, J. (2002). Sorting by prefix transpositions. International Symposium on String Processing and Information Retrieval, Springer.","DOI":"10.1007\/3-540-45735-6_7"},{"key":"ref_24","unstructured":"Whidden, C. (2007). Sorting by Transpositions: Fixed-Parameter Algorithms and Structural Properties. [Bachelor\u2019s Thesis, Dalhousie University]."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.dam.2017.07.031","article-title":"Prefix and suffix reversals on strings","volume":"246","author":"Fertin","year":"2018","journal-title":"Discret. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","article-title":"Block edit models for approximate string matching","volume":"181","author":"Lopresti","year":"1997","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","first-page":"3","article-title":"Approximating the true evolutionary distance between two genomes","volume":"12","author":"Swenson","year":"2008","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Damaschke, P. (2008). Minimum common string partition parameterized. International Workshop on Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/978-3-540-87361-7_8"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s10878-010-9370-2","article-title":"Minimum common string partition revisited","volume":"23","author":"Jiang","year":"2012","journal-title":"J. Comb. Optim."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Bulteau, L., and Komusiewicz, C. (2014, January 5\u20137). Minimum common string partition parameterized by partition size is fixed-parameter tractable. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Portland, OR, USA.","DOI":"10.1137\/1.9781611973402.8"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Bulteau, L., Fertin, G., Komusiewicz, C., and Rusu, I. (2013). A fixed-parameter algorithm for minimum common string partition with few duplications. International Workshop on Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/978-3-642-40453-5_19"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.tcs.2016.07.011","article-title":"Parameterized tractability of the maximum-duo preservation string mapping problem","volume":"646","author":"Beretta","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1109\/TCBB.2007.1075","article-title":"Removing noise and ambiguities from comparative maps in rearrangement analysis","volume":"4","author":"Zheng","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.tcs.2018.04.020","article-title":"An improved linear kernel for complementary maximal strip recovery: Simpler and smaller","volume":"786","author":"Li","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.tcs.2012.04.034","article-title":"Tractability and approximability of maximal strip recovery","volume":"440","author":"Bulteau","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"4253","DOI":"10.1016\/j.tcs.2010.09.001","article-title":"On the parameterized complexity of some optimization problems related to multiple-interval graphs","volume":"411","author":"Jiang","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Mu\u00f1oz, A., Zheng, C., Zhu, Q., Albert, V.A., Rounsley, S., and Sankoff, D. (2010). Scaffold filling, contig fusion and comparative gene order inference. BMC Bioinform., 11.","DOI":"10.1186\/1471-2105-11-304"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2014.12.005","article-title":"Fixed-parameter algorithms for scaffold filling","volume":"568","author":"Bulteau","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1089\/cmb.1998.5.555","article-title":"Multiple genome rearrangement and breakpoint phylogeny","volume":"5","author":"Sankoff","year":"1998","journal-title":"J. Comput. Biol."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"3712","DOI":"10.1073\/pnas.042692499","article-title":"On the sequencing of the human genome","volume":"99","author":"Waterston","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pcbi.0030123","article-title":"Recent Evolutions of Multiple Sequence Alignment Algorithms","volume":"3","author":"Notredame","year":"2007","journal-title":"PLOS Comput. Biol."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0304-3975(99)00324-2","article-title":"The complexity of multiple sequence alignment with SP-score that is a metric","volume":"259","author":"Bonizzoni","year":"2001","journal-title":"Theor. Comput. Sci."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1089\/106652701753307511","article-title":"Computational complexity of multiple sequence alignment with SP-score","volume":"8","author":"Just","year":"2001","journal-title":"J. Comput. Biol."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Elias, I. (2003). Settling the intractability of multiple alignment. International Symposium on Algorithms and Computation, Springer.","DOI":"10.1007\/978-3-540-24587-2_37"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"2455","DOI":"10.1093\/bioinformatics\/btp452","article-title":"Upcoming challenges for multiple sequence alignment methods in the high-throughput era","volume":"25","author":"Kemena","year":"2009","journal-title":"Bioinformatics"},{"key":"ref_46","first-page":"1","article-title":"Multivariate Algorithmics for NP-Hard String Problems","volume":"114","author":"Bulteau","year":"2014","journal-title":"Bull. EATCS"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02679443","article-title":"On covering problems of codes","volume":"30","author":"Frances","year":"1997","journal-title":"Theory Comput. Syst."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s00453-003-1028-3","article-title":"Fixed-parameter algorithms for closest string and related problems","volume":"37","author":"Gramm","year":"2003","journal-title":"Algorithmica"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/S0304-3975(03)00320-7","article-title":"On the complexity of finding common approximate substrings","volume":"306","author":"Evans","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/s00493-006-0011-4","article-title":"On the parameterized intractability of motif search problems","volume":"26","author":"Fellows","year":"2006","journal-title":"Combinatorica"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"1382","DOI":"10.1137\/060673898","article-title":"Closest substring problems with small distances","volume":"38","author":"Marx","year":"2008","journal-title":"SIAM J. Comput."},{"key":"ref_52","first-page":"13","article-title":"Finding consensus strings with small length difference between input and solution strings","volume":"9","author":"Schmid","year":"2017","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Boucher, C., and Ma, B. (2011). Closest string with outliers. BMC Bioinform., 12.","DOI":"10.1186\/1471-2105-12-S1-S55"},{"key":"ref_54","unstructured":"Bulteau, L., and Schmid, M. (2018, January 27\u201331). Consensus Strings with Small Maximum Distance and Small Distance Sum. Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK."},{"key":"ref_55","unstructured":"Chen, J., Hermelin, D., and Sorge, M. (2019, January 9\u201311). On Computing Centroids According to the p-Norms of Hamming Distance Vectors. Proceedings of the 27th Annual European Symposium on Algorithms, ESA 2019, Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Munich\/Garching, Germany."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","article-title":"On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems","volume":"67","author":"Pietrzak","year":"2003","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","article-title":"The parameterized complexity of sequence alignment and consensus","volume":"147","author":"Bodlaender","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Irving, R.W., and Fraser, C.B. (1992). Two algorithms for the longest common subsequence of three (or more) strings. Annual Symposium on Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/3-540-56024-6_18"},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., and Williams, V.V. (2015, January 17\u201320). Tight hardness results for LCS and other sequence similarity measures. Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2015.14"},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Bringmann, K., and K\u00fcnnemann, M. (2018, January 7\u201310). Multivariate fine-grained complexity of longest common subsequence. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.79"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2017.05.017","article-title":"Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs","volume":"689","author":"Giannopoulou","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"ref_62","first-page":"46:1","article-title":"The Power of Linear-Time Data Reduction for Maximum Matching","volume":"Volume 83","author":"Mertzios","year":"2017","journal-title":"Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)"},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"33:1","DOI":"10.1145\/3310228","article-title":"Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs","volume":"15","author":"Coudert","year":"2019","journal-title":"ACM Trans. Algorithms"},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","article-title":"The constrained longest common subsequence problem","volume":"88","author":"Tsai","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1016\/j.ipl.2010.07.015","article-title":"Variants of constrained longest common subsequence","volume":"110","author":"Bonizzoni","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s10878-009-9262-5","article-title":"On the generalized constrained longest common subsequence problems","volume":"21","author":"Chen","year":"2011","journal-title":"J. Comb. Optim."},{"key":"ref_67","doi-asserted-by":"crossref","unstructured":"Gotthilf, Z., Hermelin, D., Landau, G.M., and Lewenstein, M. (2010). Restricted lcs. International Symposium on String Processing and Information Retrieval, Springer.","DOI":"10.1007\/978-3-642-16321-0_26"},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/s10878-006-7137-6","article-title":"On the computational hardness based on linear FPT-reductions","volume":"11","author":"Chen","year":"2006","journal-title":"J. Comb. Optim."},{"key":"ref_69","doi-asserted-by":"crossref","unstructured":"Fellows, M., Hallett, M., Korostensky, C., and Stege, U. (1998). Analogs and Duals of the MAST Problem for Sequences and Trees. European Symposium on Algorithms, Springer.","DOI":"10.1007\/3-540-68530-8_9"},{"key":"ref_70","doi-asserted-by":"crossref","unstructured":"Nicolas, F., and Rivals, E. (2003). Complexities of the centre and median string problems. Annual Symposium on Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/3-540-44888-8_23"},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Maji, H., and Izumi, T. (2015). Listing center strings under the edit distance metric. Combinatorial Optimization and Applications, Springer.","DOI":"10.1007\/978-3-319-26626-8_57"},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"R42","DOI":"10.1186\/gb-2014-15-3-r42","article-title":"A comprehensive evaluation of assembly scaffolding tools","volume":"15","author":"Hunt","year":"2014","journal-title":"Genome Biol."},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1145\/585265.585267","article-title":"The Greedy Path-merging Algorithm for Contig Scaffolding","volume":"49","author":"Huson","year":"2002","journal-title":"J. ACM"},{"key":"ref_74","unstructured":"Chateau, A., Giroudeau, R., Poss, M., and Weller, M. Scaffolding with repeated contigs using flow formulations, unpublished manuscript."},{"key":"ref_75","doi-asserted-by":"crossref","first-page":"1771","DOI":"10.1007\/s00453-018-0405-x","article-title":"Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases","volume":"80","author":"Weller","year":"2018","journal-title":"Algorithmica"},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"1681","DOI":"10.1089\/cmb.2011.0170","article-title":"Opera: Reconstructing Optimal Genomic Scaffolds with High-Throughput Paired-End Sequences","volume":"18","author":"Gao","year":"2011","journal-title":"J. Comput. Biol."},{"key":"ref_77","doi-asserted-by":"crossref","unstructured":"Weller, M., Chateau, A., and Giroudeau, R. (2015). Exact approaches for scaffolding. BMC Bioinform., 16.","DOI":"10.1186\/1471-2105-16-S14-S2"},{"key":"ref_78","doi-asserted-by":"crossref","unstructured":"Weller, M., Chateau, A., and Giroudeau, R. (2017, January 16\u201318). On the Linearization of Scaffolds Sharing Repeated Contigs. Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA\u201917) Part II, Shanghai, China.","DOI":"10.1007\/978-3-319-71147-8_38"},{"key":"ref_79","unstructured":"Davot, T., Chateau, A., Giroudeau, R., and Weller, M. (2019, January 27\u201330). Linearizing Genomes: Exact Methods and Local Search. Proceedings of the SOFSEM\u201920, Nov\u00fd Smokovec, Slovakia."},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1093\/bioinformatics\/bts716","article-title":"SCARPA: scaffolding reads with practical algorithms","volume":"29","author":"Donmez","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_81","doi-asserted-by":"crossref","first-page":"14515","DOI":"10.1038\/ncomms14515","article-title":"Scaffolding and completing genome assemblies in real-time with nanopore sequencing","volume":"8","author":"Cao","year":"2017","journal-title":"Nat. Commun."},{"key":"ref_82","doi-asserted-by":"crossref","unstructured":"Dallard, C., Weller, M., Chateau, A., and Giroudeau, R. (2016). Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding. Combinatorial Optimization and Applications, Springer International Publishing.","DOI":"10.1007\/978-3-319-48749-6_22"},{"key":"ref_83","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1534\/genetics.109.110510","article-title":"Human triallelic sites: Evidence for a new mutational mechanism?","volume":"184","author":"Hodgkinson","year":"2010","journal-title":"Genetics"},{"key":"ref_84","unstructured":"International SNP Map Working Group (2001). A map of human genome sequence variation containing 1.42 million single nucleotide polymorphisms. Nature, 409, 928."},{"key":"ref_85","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1002\/gepi.20185","article-title":"Understanding the accuracy of statistical haplotype inference with sequence data of known phase","volume":"31","author":"Clark","year":"2007","journal-title":"Genet. Epidemiol."},{"key":"ref_86","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1093\/genetics\/165.2.915","article-title":"Analysis and Exploration of the Use of Rule-Based Algorithms and Consensus Methods for the Inferral of Haplotypes","volume":"165","author":"Orzack","year":"2003","journal-title":"Genetics"},{"key":"ref_87","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1093\/bioinformatics\/btn572","article-title":"How frugal is mother nature with haplotypes?","volume":"25","author":"Climer","year":"2008","journal-title":"Bioinformatics"},{"key":"ref_88","doi-asserted-by":"crossref","first-page":"105","DOI":"10.2174\/157489306775330570","article-title":"Models and Algorithms for Haplotyping Problem","volume":"1","author":"Zhang","year":"2006","journal-title":"Curr. Bioinform."},{"key":"ref_89","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, B.V., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., and Istrail, S. (2004). A Survey of Computational Methods for Determining Haplotypes. Computational Methods for SNPs and Haplotype Inference, Springer.","DOI":"10.1007\/978-3-540-24719-7_3"},{"key":"ref_90","doi-asserted-by":"crossref","unstructured":"Lancia, G. (2016). Algorithmic approaches for the single individual haplotyping problem. RAIRO Recherche Op\u00e9rationnelle, 50.","DOI":"10.1051\/ro\/2015037"},{"key":"ref_91","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/s11704-007-0027-y","article-title":"An overview of the haplotype problems and algorithms","volume":"1","author":"Zhao","year":"2007","journal-title":"Front. Comput. Sci. China"},{"key":"ref_92","doi-asserted-by":"crossref","first-page":"23","DOI":"10.4310\/CIS.2010.v10.n1.a2","article-title":"Theory and Algorithms for the Haplotype Assembly Problem","volume":"10","author":"Schwartz","year":"2010","journal-title":"Commun. Inf. Syst."},{"key":"ref_93","doi-asserted-by":"crossref","first-page":"2217","DOI":"10.1093\/bioinformatics\/btq411","article-title":"A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem","volume":"26","author":"Geraci","year":"2010","journal-title":"Bioinformatics"},{"key":"ref_94","doi-asserted-by":"crossref","first-page":"18","DOI":"10.2174\/157489310790596411","article-title":"Computational Models and Algorithms for the Single Individual Haplotyping Problem","volume":"5","author":"Xie","year":"2010","journal-title":"Curr. Bioinform."},{"key":"ref_95","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s13258-015-0342-x","article-title":"Survey of computational haplotype determination methods for single individual","volume":"38","author":"Rhee","year":"2016","journal-title":"Genes Genom."},{"key":"ref_96","doi-asserted-by":"crossref","unstructured":"Lancia, G., Bafna, V., Istrail, S., Lippert, R., and Schwartz, R. (2001). SNPs Problems, Complexity, and Algorithms. Algorithms\u2014ESA 2001, Springer.","DOI":"10.1007\/3-540-44676-1_15"},{"key":"ref_97","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.tcs.2004.12.017","article-title":"Polynomial and APX-hard cases of the individual haplotyping problem","volume":"335","author":"Bafna","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_98","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/s00453-007-9150-2","article-title":"An Improved (and Practical) Parameterized Algorithm for the Individual Haplotyping Problem MFR with Mate-Pairs","volume":"52","author":"Xie","year":"2008","journal-title":"Algorithmica"},{"key":"ref_99","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","article-title":"Finding odd cycle transversals","volume":"32","author":"Reed","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"ref_100","doi-asserted-by":"crossref","first-page":"77","DOI":"10.7155\/jgaa.00177","article-title":"Algorithm Engineering for Optimal Graph Bipartization","volume":"13","year":"2009","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_101","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/2566616","article-title":"Faster Parameterized Algorithms Using Linear Programming","volume":"11","author":"Lokshtanov","year":"2014","journal-title":"ACM Trans. Algorithms"},{"key":"ref_102","doi-asserted-by":"crossref","first-page":"20:1","DOI":"10.1145\/2635810","article-title":"Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal","volume":"10","author":"Kratsch","year":"2014","journal-title":"ACM Trans. Algorithms"},{"key":"ref_103","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1142\/S0219720007002710","article-title":"Research on parameterized algorithms of the individual haplotyping problem","volume":"5","author":"Xie","year":"2007","journal-title":"J. Bioinform. Comput. Biol."},{"key":"ref_104","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/s00453-007-0029-z","article-title":"The Complexity of the Single Individual SNP Haplotyping Problem","volume":"49","author":"Cilibrasi","year":"2007","journal-title":"Algorithmica"},{"key":"ref_105","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1089\/cmb.2015.0220","article-title":"On the Minimum Error Correction Problem for Haplotype Assembly in Diploid and Polyploid Genomes","volume":"23","author":"Bonizzoni","year":"2016","journal-title":"J. Comput. Biol."},{"key":"ref_106","doi-asserted-by":"crossref","first-page":"2456","DOI":"10.1093\/bioinformatics\/bti352","article-title":"Haplotype reconstruction from SNP fragments by minimum error correction","volume":"21","author":"Wang","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_107","doi-asserted-by":"crossref","first-page":"i105","DOI":"10.1093\/bioinformatics\/btn147","article-title":"A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments and genotype with errors","volume":"24","author":"Xie","year":"2008","journal-title":"Bioinformatics"},{"key":"ref_108","doi-asserted-by":"crossref","unstructured":"Deng, F., Cui, W., and Wang, L. (2013). A highly accurate heuristic algorithm for the haplotype assembly problem. BMC Genom., 14.","DOI":"10.1186\/1471-2164-14-S2-S2"},{"key":"ref_109","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1089\/cmb.2014.0157","article-title":"WhatsHap: Weighted Haplotype Assembly for Future-Generation Sequencing Reads","volume":"22","author":"Patterson","year":"2015","journal-title":"J. Comput. Biol."},{"key":"ref_110","doi-asserted-by":"crossref","first-page":"1610","DOI":"10.1093\/bioinformatics\/btv495","article-title":"HapCol: accurate and memory-efficient haplotype assembly from long reads","volume":"32","author":"Pirola","year":"2015","journal-title":"Bioinformatics"},{"key":"ref_111","doi-asserted-by":"crossref","first-page":"i105","DOI":"10.1093\/bioinformatics\/bty279","article-title":"A graph-based approach to diploid genome assembly","volume":"34","author":"Garg","year":"2018","journal-title":"Bioinformatics"},{"key":"ref_112","doi-asserted-by":"crossref","first-page":"i183","DOI":"10.1093\/bioinformatics\/btq215","article-title":"Optimal algorithms for haplotype assembly from whole-genome sequence data","volume":"26","author":"He","year":"2010","journal-title":"Bioinformatics"},{"key":"ref_113","doi-asserted-by":"crossref","unstructured":"Zhang, X.S., Wang, R.S., Wu, L.Y., and Zhang, W. (2006). Minimum Conflict Individual Haplotyping from SNP Fragments and Related Genotype. Evolut. Bioinform., 2.","DOI":"10.1177\/117693430600200032"},{"key":"ref_114","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.tcs.2015.06.043","article-title":"Parameterized complexity analysis for the Closest String with Wildcards problem","volume":"600","author":"Hermelin","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_115","doi-asserted-by":"crossref","first-page":"i234","DOI":"10.1093\/bioinformatics\/btw276","article-title":"Read-based phasing of related individuals","volume":"32","author":"Garg","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_116","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/s10255-006-0315-6","article-title":"A Dynamic Programming Algorithm for the k-Haplotyping Problem","volume":"22","author":"Li","year":"2006","journal-title":"Acta Mathematicae Applicatae Sinica"},{"key":"ref_117","doi-asserted-by":"crossref","first-page":"CIN.S13779","DOI":"10.4137\/CIN.S13779","article-title":"Review of Current Methods, Applications, and Data Management for the Bioinformatics Analysis of Whole Exome Sequencing","volume":"13s2","author":"Bao","year":"2014","journal-title":"Cancer Inform."},{"key":"ref_118","unstructured":"Garg, S. (2018). Computational Haplotyping: Theory and Practice. [Ph.D. Thesis, Universit\u00e4t des Saarlandes]."},{"key":"ref_119","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (2003). Haplotype Inference by Pure Parsimony. Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/3-540-44888-8_11"},{"key":"ref_120","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1109\/TCBB.2010.52","article-title":"Pure Parsimony Xor Haplotyping","volume":"7","author":"Bonizzoni","year":"2010","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_121","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1089\/cmb.2009.0101","article-title":"Haplotype Inference by Pure Parsimony: A Survey","volume":"17","author":"Lynce","year":"2010","journal-title":"J. Comput. Biol."},{"key":"ref_122","unstructured":"Hubbell, E. Finding a Parsimony Solution to Haplotype Phase is NP-Hard. Personal communication."},{"key":"ref_123","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","article-title":"Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms","volume":"16","author":"Lancia","year":"2004","journal-title":"INFORMS J. Comput."},{"key":"ref_124","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1089\/cmb.2005.12.1261","article-title":"An Approximation Algorithm for Haplotype Inference by Maximum Parsimony","volume":"12","author":"Huang","year":"2005","journal-title":"J. Comput. Biol."},{"key":"ref_125","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1109\/TCBB.2006.40","article-title":"Islands of Tractability for Parsimony Haplotyping","volume":"3","author":"Sharan","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_126","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1109\/TCBB.2007.70232","article-title":"Shorelines of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems","volume":"5","author":"Keijsper","year":"2008","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_127","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.orl.2005.05.007","article-title":"A polynomial case of the parsimony haplotyping problem","volume":"34","author":"Lancia","year":"2006","journal-title":"Oper. Res. Lett."},{"key":"ref_128","unstructured":"van Iersel, L.J.J. (2009). Algorithms, Haplotypes and Phylogenetic Networks. [Ph.D. Thesis, Eindhoven University of Technology]."},{"key":"ref_129","doi-asserted-by":"crossref","first-page":"1692","DOI":"10.1109\/TCBB.2010.72","article-title":"Haplotype Inference Constrained by Plausible Haplotype Data","volume":"8","author":"Fellows","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_130","doi-asserted-by":"crossref","unstructured":"Fleischer, R., Guo, J., Niedermeier, R., Uhlmann, J., Wang, Y., Weller, M., and Wu, X. (2010). Extended Islands of Tractability for Parsimony Haplotyping. Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/978-3-642-13509-5_20"},{"key":"ref_131","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (2002, January 18\u201321). Haplotyping As Perfect Phylogeny: Conceptual Framework and Efficient Solutions. Proceedings of the Sixth Annual International Conference on Computational Biology, RECOMB \u201902, Washington, DC, USA.","DOI":"10.1145\/565196.565218"},{"key":"ref_132","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1089\/cmb.2006.13.522","article-title":"A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem","volume":"13","author":"Ding","year":"2006","journal-title":"J. Comput. Biol."},{"key":"ref_133","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s00453-007-0094-3","article-title":"A Linear-Time Algorithm for the Perfect Phylogeny Haplotype Problem","volume":"48","author":"Bonizzoni","year":"2007","journal-title":"Algorithmica"},{"key":"ref_134","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00453-012-9730-7","article-title":"The Parameterized Complexity of the Shared Center Problem","volume":"69","author":"Chen","year":"2014","journal-title":"Algorithmica"},{"key":"ref_135","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1109\/TCBB.2014.2352031","article-title":"Tractable Cases of (*, 2)-Bounded Parsimony Haplotyping","volume":"12","author":"Keijsper","year":"2015","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_136","unstructured":"Cicalese, F., and Milanivc, M. (2008). On Parsimony Haplotyping, Universit\u1e97 Bielefeld. Technical Report."},{"key":"ref_137","doi-asserted-by":"crossref","unstructured":"Haeckel, E. (1866). Generelle Morphologie der Organismen. Allgemeine Grundz\u00fcge der organischen Formen-Wissenschaft, mechanisch begr\u00fcndet durch die von C. Darwin reformirte Descendenz-Theorie, etc., Verlag von Georg Reimer.","DOI":"10.5962\/bhl.title.3953"},{"key":"ref_138","doi-asserted-by":"crossref","first-page":"125","DOI":"10.2307\/4444260","article-title":"Nothing in Biology Makes Sense except in the Light of Evolution","volume":"35","author":"Dobzhansky","year":"1973","journal-title":"Am. Biol. Teach."},{"key":"ref_139","doi-asserted-by":"crossref","unstructured":"De Bruyn, A., Martin, D.P., and Lefeuvre, P. (2014). Phylogenetic Reconstruction Methods: An Overview. Molecular Plant Taxonomy: Methods and Protocols, Humana Press.","DOI":"10.1007\/978-1-62703-767-9_13"},{"key":"ref_140","doi-asserted-by":"crossref","unstructured":"Huson, D.H., Rupp, R., and Scornavacca, C. (2010). Phylogenetic Networks\u2014Concepts, Algorithms and Applications, Cambridge University Press.","DOI":"10.1017\/CBO9780511974076"},{"key":"ref_141","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.tcs.2004.12.012","article-title":"Computing the maximum agreement of phylogenetic networks","volume":"335","author":"Choy","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_142","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1016\/j.jcss.2010.07.005","article-title":"Average parameterization and partial kernelization for computing medians","volume":"77","author":"Betzler","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_143","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1090\/dimacs\/061\/11","article-title":"A classification of consensus methods for phylogenetics","volume":"61","author":"Bryant","year":"2003","journal-title":"DIMACS Ser. Discrete Math. Theor. Comput. Sci."},{"key":"ref_144","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/B978-0-12-800049-6.00219-5","article-title":"Consensus Methods, Phylogenetic","volume":"Volume 1","author":"Degnan","year":"2016","journal-title":"Encyclopedia of Evolutionary Biology"},{"key":"ref_145","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","article-title":"The complexity of reconstructing trees from qualitative characters and subtrees","volume":"9","author":"Steel","year":"1992","journal-title":"J. Classif."},{"key":"ref_146","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1006\/jagm.2000.1116","article-title":"Algorithmic Aspects of Tree Amalgamation","volume":"37","author":"Bryant","year":"2000","journal-title":"J. Algorithms"},{"key":"ref_147","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","article-title":"Easy problems for tree-decomposable graphs","volume":"12","author":"Arnborg","year":"1991","journal-title":"J. Algorithms"},{"key":"ref_148","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inf. Comput."},{"key":"ref_149","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.tcs.2005.10.033","article-title":"Compatibility of unrooted phylogenetic trees is FPT","volume":"351","author":"Bryant","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_150","doi-asserted-by":"crossref","first-page":"385","DOI":"10.7155\/jgaa.00327","article-title":"The agreement problem for unrooted phylogenetic trees is FPT","volume":"18","author":"Scornavacca","year":"2014","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_151","doi-asserted-by":"crossref","unstructured":"Baste, J., Paul, C., Sau, I., and Scornavacca, C. (2016). Efficient FPT Algorithms for (Strict) Compatibility of Unrooted Phylogenetic Trees. Algorithmic Aspects in Information and Management, Springer International Publishing.","DOI":"10.1007\/978-3-319-41168-2_5"},{"key":"ref_152","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","article-title":"Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions","volume":"10","author":"Aho","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_153","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0166-218X(95)00074-2","article-title":"Reconstruction of rooted trees from subtrees","volume":"69","author":"Ng","year":"1996","journal-title":"Discret. Appl. Math."},{"key":"ref_154","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1093\/sysbio\/46.3.523","article-title":"Gene Trees in Species Trees","volume":"46","author":"Maddison","year":"1997","journal-title":"Syst. Biol."},{"key":"ref_155","doi-asserted-by":"crossref","first-page":"1700","DOI":"10.3732\/ajb.91.10.1700","article-title":"Reconstructing patterns of reticulate evolution in plants","volume":"91","author":"Linder","year":"2004","journal-title":"Am. J. Bot."},{"key":"ref_156","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/S1571-0653(04)00222-7","article-title":"On the complexity of inferring rooted evolutionary trees","volume":"7","author":"Jansson","year":"2001","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_157","unstructured":"Bryant, D. (1997). Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis. [Ph.D. Thesis, University of Canterbury]."},{"key":"ref_158","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1023\/B:JOCO.0000021936.04215.68","article-title":"Constructing the Maximum Consensus Tree from Rooted Triples","volume":"8","author":"Wu","year":"2004","journal-title":"J. Comb. Optim."},{"key":"ref_159","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1016\/j.dam.2010.03.004","article-title":"New results on optimizing rooted triplets consistency","volume":"158","author":"Byrka","year":"2010","journal-title":"Discret. Appl. Math."},{"key":"ref_160","doi-asserted-by":"crossref","unstructured":"Guillemot, S., and Mnich, M. (2010). Kernel and Fast Algorithm for Dense Triplet Inconsistency. Theory and Applications of Models of Computation, Springer.","DOI":"10.1007\/978-3-642-13562-0_23"},{"key":"ref_161","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., and Zehavi, M. (2019). Kernelization: Theory of Parameterized Preprocessing, Cambridge University Press.","DOI":"10.1017\/9781107415157"},{"key":"ref_162","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1016\/j.jcss.2015.08.002","article-title":"Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique","volume":"82","author":"Paul","year":"2016","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_163","doi-asserted-by":"crossref","first-page":"1250013","DOI":"10.1142\/S0219720012500138","article-title":"Constructing a minimum phylogenetic network from a dense triplet set","volume":"10","author":"Habib","year":"2012","journal-title":"J. Bioinform. Comput. Biol."},{"key":"ref_164","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00453-009-9333-0","article-title":"Constructing the Simplest Possible Phylogenetic Network from Triplets","volume":"60","author":"Kelk","year":"2011","journal-title":"Algorithmica"},{"key":"ref_165","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1016\/S0022-0000(03)00077-1","article-title":"A fixed-parameter algorithm for minimum quartet inconsistency","volume":"67","author":"Gramm","year":"2003","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_166","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00453-004-1147-5","article-title":"Rooted Maximum Agreement Supertrees","volume":"43","author":"Jansson","year":"2005","journal-title":"Algorithmica"},{"key":"ref_167","first-page":"126","article-title":"Distributions of Tree Comparison Metrics\u2014Some New Results","volume":"42","author":"Steel","year":"1993","journal-title":"Syst. Biol."},{"key":"ref_168","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0025-5564(94)90012-4","article-title":"The agreement metric for labeled binary trees","volume":"123","author":"Goddard","year":"1994","journal-title":"Math. Biosci."},{"key":"ref_169","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1016\/j.jda.2006.08.005","article-title":"Maximum agreement and compatible supertrees","volume":"5","author":"Berry","year":"2007","journal-title":"J. Discret. Algorithms"},{"key":"ref_170","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1109\/TCBB.2010.30","article-title":"Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem","volume":"7","author":"Guillemot","year":"2010","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_171","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00453-009-9303-6","article-title":"Improved Algorithms for Maximum Agreement and\u00c2 Compatible Supertrees","volume":"59","author":"Hoang","year":"2011","journal-title":"Algorithmica"},{"key":"ref_172","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/120897559","article-title":"Fixed-Parameter Algorithms for Finding Agreement Supertrees","volume":"44","author":"Guillemot","year":"2015","journal-title":"SIAM J. Comput."},{"key":"ref_173","doi-asserted-by":"crossref","first-page":"1656","DOI":"10.1137\/S0097539794269461","article-title":"Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms","volume":"26","author":"Amir","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_174","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","article-title":"On the agreement of many trees","volume":"55","author":"Farach","year":"1995","journal-title":"Inf. Process. Lett."},{"key":"ref_175","unstructured":"Wang, B., and Swenson, K.M. (2019). A Faster Algorithm for Computing the Kernel of Maximum Agreement Subtrees. IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_176","first-page":"73","article-title":"Computational Tractability: The View From Mars","volume":"69","author":"Downey","year":"1999","journal-title":"Bull. EATCS"},{"key":"ref_177","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","article-title":"Faster exact algorithms for hard problems: A parameterized point of view","volume":"229","author":"Alber","year":"2001","journal-title":"Discret. Math."},{"key":"ref_178","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1109\/TCBB.2006.39","article-title":"Improved Parameterized Complexity of the Maximum Agreement Subtree and Maximum Compatible Tree Problems","volume":"3","author":"Berry","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_179","doi-asserted-by":"crossref","unstructured":"Chauve, C., Jones, M., Lafond, M., Scornavacca, C., and Weller, M. (2017). Constructing a Consensus Phylogeny from a Leaf-Removal Distance. CoRR.","DOI":"10.1007\/978-3-319-67428-5_12"},{"key":"ref_180","doi-asserted-by":"crossref","unstructured":"Chen, Z.Z., Ueta, S., Li, J., Wang, L., Skums, P., and Li, M. (2019). Computing a Consensus Phylogeny via Leaf Removal. Bioinformatics Research and Applications, Springer International Publishing.","DOI":"10.1007\/978-3-030-20242-2_1"},{"key":"ref_181","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.tcs.2018.08.006","article-title":"The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics","volume":"760","author":"Lafond","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_182","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1109\/TST.2013.6616522","article-title":"Distances between phylogenetic trees: A survey","volume":"18","author":"Shi","year":"2013","journal-title":"Tsinghua Sci.Technol."},{"key":"ref_183","unstructured":"Whidden, C. (2013). Efficient Computation and Application of Maximum Agreement Forests. [Ph.D. Thesis, Dalhousie University]."},{"key":"ref_184","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","article-title":"On the complexity of comparing evolutionary trees","volume":"71","author":"Hein","year":"1996","journal-title":"Discret. Appl. Math."},{"key":"ref_185","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","article-title":"Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees","volume":"5","author":"Allen","year":"2001","journal-title":"Ann. Comb."},{"key":"ref_186","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/s00224-007-1329-z","article-title":"A Faster FPT Algorithm for the Maximum Agreement Forest Problem","volume":"41","author":"Hallett","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_187","doi-asserted-by":"crossref","unstructured":"Whidden, C., and Zeh, N. (2009). A Unifying View on Approximation and FPT of Agreement Forests. Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/978-3-642-04241-6_32"},{"key":"ref_188","doi-asserted-by":"crossref","unstructured":"Kelk, S., and Linz, S. (2018). A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees. CoRR.","DOI":"10.1137\/18M122724X"},{"key":"ref_189","doi-asserted-by":"crossref","unstructured":"Kelk, S., and Linz, S. (2019). New reduction rules for the tree bisection and reconnection distance. arXiv.","DOI":"10.1007\/s00026-020-00502-7"},{"key":"ref_190","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2013.12.025","article-title":"Algorithms for parameterized maximum agreement forest problem on multiple trees","volume":"554","author":"Shi","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_191","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1016\/j.tcs.2014.10.031","article-title":"Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees","volume":"562","author":"Chen","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_192","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s00285-005-0315-9","article-title":"Bounding the Number of Hybridisation Events for a Consistent Evolutionary History","volume":"51","author":"Baroni","year":"2005","journal-title":"J. Math. Biol."},{"key":"ref_193","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00026-004-0229-z","article-title":"On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance","volume":"8","author":"Bordewich","year":"2005","journal-title":"Ann. Comb."},{"key":"ref_194","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1016\/j.jda.2007.10.002","article-title":"A 3-approximation algorithm for the subtree distance between phylogenies","volume":"6","author":"Bordewich","year":"2008","journal-title":"J. Discret. Algorithms"},{"key":"ref_195","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1137\/110845045","article-title":"Fixed-Parameter Algorithms for Maximum Agreement Forests","volume":"42","author":"Whidden","year":"2013","journal-title":"SIAM J. Comput."},{"key":"ref_196","doi-asserted-by":"crossref","unstructured":"Chen, Z.Z., and Wang, L. (2013). Faster Exact Computation of rSPR Distance. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Springer.","DOI":"10.1007\/978-3-642-38756-2_7"},{"key":"ref_197","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1109\/TCBB.2011.137","article-title":"Algorithms for Reticulate Networks of Multiple Phylogenetic Trees","volume":"9","author":"Chen","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_198","unstructured":"Collins, J.S. (2009). Rekernelisation Algorithms in Hybrid Phylogenies. [Ph.D. Thesis, University of Canterbury]."},{"key":"ref_199","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/120903567","article-title":"Approximation Algorithms for Nonbinary Agreement Forests","volume":"28","author":"Kelk","year":"2014","journal-title":"SIAM J. Discret. Math."},{"key":"ref_200","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1007\/s00453-015-9983-z","article-title":"Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees","volume":"74","author":"Whidden","year":"2016","journal-title":"Algorithmica"},{"key":"ref_201","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1109\/tcbb.2007.1019","article-title":"Computing the Hybridization Number of Two Phylogenetic Trees Is Fixed-Parameter Tractable","volume":"4","author":"Bordewich","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_202","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.jcss.2018.03.002","article-title":"A parameterized algorithm for the Maximum Agreement Forest problem on multiple rooted multifurcating trees","volume":"97","author":"Shi","year":"2018","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_203","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/TCBB.2008.86","article-title":"Hybridization in Nonbinary Trees","volume":"6","author":"Linz","year":"2009","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_204","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.dam.2006.08.008","article-title":"Computing the minimum number of hybridization events for a consistent evolutionary history","volume":"155","author":"Bordewich","year":"2007","journal-title":"Discret. Appl. Math."},{"key":"ref_205","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1093\/bioinformatics\/btr618","article-title":"Fast computation of minimum hybridization networks","volume":"28","author":"Albrecht","year":"2011","journal-title":"Bioinformatics"},{"key":"ref_206","doi-asserted-by":"crossref","first-page":"1607","DOI":"10.1137\/15M1036579","article-title":"Hybridization Number on Three Rooted Binary Trees is EPT","volume":"30","author":"Kelk","year":"2016","journal-title":"SIAM J. Discret. Math."},{"key":"ref_207","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/j.ipl.2013.02.010","article-title":"A quadratic kernel for computing the hybridization number of multiple trees","volume":"113","author":"Linz","year":"2013","journal-title":"Inf. Process. Lett."},{"key":"ref_208","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1016\/j.jcss.2016.03.006","article-title":"Kernelizations for the hybridization number problem on multiple nonbinary trees","volume":"82","author":"Kelk","year":"2016","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_209","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","article-title":"Solving MAX-r-SAT Above a Tight Lower Bound","volume":"61","author":"Alon","year":"2011","journal-title":"Algorithmica"},{"key":"ref_210","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/TCBB.2012.134","article-title":"A Simple Fixed Parameter Tractable Algorithm for Computing the Hybridization Number of Two (Not Necessarily Binary) Trees","volume":"10","author":"Piovesan","year":"2013","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_211","unstructured":"Li, Z. (2014). Fixed-Parameter Algorithm for Hybridization Number of Two Multifurcating Trees. [Master\u2019s Thesis, Dalhousie University]."},{"key":"ref_212","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s00285-016-1023-3","article-title":"On the fixed parameter tractability of agreement-based phylogenetic distances","volume":"74","author":"Bordewich","year":"2017","journal-title":"J. Math. Biol."},{"key":"ref_213","doi-asserted-by":"crossref","first-page":"189","DOI":"10.7155\/jgaa.00390","article-title":"Phylogenetic incongruence through the lens of Monadic Second Order logic","volume":"20","author":"Kelk","year":"2016","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_214","doi-asserted-by":"crossref","unstructured":"Klawitter, J., and Linz, S. (2018). On the Subnet Prune and Regraft Distance. arXiv.","DOI":"10.37236\/7860"},{"key":"ref_215","doi-asserted-by":"crossref","first-page":"EBO.S419","DOI":"10.4137\/EBO.S419","article-title":"SPR Distance Computation for Unrooted Trees","volume":"4","author":"Hickey","year":"2008","journal-title":"Evolut. Bioinform."},{"key":"ref_216","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1109\/TCBB.2008.132","article-title":"On the Complexity of uSPR Distance","volume":"7","author":"Bonet","year":"2010","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_217","unstructured":"Whidden, C., and Matsen, F. (2016). Chain Reduction Preserves the Unrooted Subtree Prune-and-Regraft Distance. arXiv."},{"key":"ref_218","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1109\/TCBB.2018.2802911","article-title":"Calculating the Unrooted Subtree Prune-and-Regraft Distance","volume":"16","author":"Whidden","year":"2019","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_219","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/j.dam.2019.01.031","article-title":"Deciding the existence of a cherry-picking sequence is hard on two trees","volume":"260","author":"Kelk","year":"2019","journal-title":"Discret. Appl. Math."},{"key":"ref_220","doi-asserted-by":"crossref","first-page":"1879","DOI":"10.1007\/s11538-013-9874-x","article-title":"Cherry Picking: A Characterization of the Temporal Hybridization Number for a Set of Phylogenies","volume":"75","author":"Humphries","year":"2013","journal-title":"Bull. Math. Biol."},{"key":"ref_221","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s00026-015-0298-1","article-title":"On the Maximum Parsimony Distance Between Phylogenetic Trees","volume":"20","author":"Fischer","year":"2016","journal-title":"Ann. Comb."},{"key":"ref_222","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/s00026-017-0361-1","article-title":"On the Complexity of Computing MP Distance Between Binary Phylogenetic Trees","volume":"21","author":"Kelk","year":"2017","journal-title":"Ann. Comb."},{"key":"ref_223","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2016.07.010","article-title":"Reduction rules for the maximum parsimony distance on phylogenetic trees","volume":"646","author":"Kelk","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_224","doi-asserted-by":"crossref","first-page":"715","DOI":"10.7155\/jgaa.00508","article-title":"Treewidth of display graphs: bounds, brambles and applications","volume":"23","author":"Janssen","year":"2019","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_225","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1137\/S0097539798343362","article-title":"From Gene Trees to Species Trees","volume":"30","author":"Ma","year":"2000","journal-title":"SIAM J. Comput."},{"key":"ref_226","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.tcs.2005.05.016","article-title":"Reconciling a gene tree to a species tree under the duplication cost model","volume":"347","author":"Bonizzoni","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_227","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1093\/bib\/bbr045","article-title":"Models, algorithms and programs for phylogeny reconciliation","volume":"12","author":"Doyon","year":"2011","journal-title":"Brief. Bioinform."},{"key":"ref_228","first-page":"e42","article-title":"The Inference of Gene Trees with Species Trees","volume":"64","author":"Tannier","year":"2014","journal-title":"Syst. Biol."},{"key":"ref_229","doi-asserted-by":"crossref","first-page":"642089","DOI":"10.1155\/2014\/642089","article-title":"Reconciliation of gene and species trees","volume":"2014","author":"Rusin","year":"2014","journal-title":"BioMed Res. Int."},{"key":"ref_230","unstructured":"Scornavacca, C. (2019). Phylogenomics among Trees and Networks: A Challenging Accrobranche, in press."},{"key":"ref_231","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.tcs.2006.05.019","article-title":"DLS-trees: A model of evolutionary scenarios","volume":"359","author":"Tiuryn","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_232","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1089\/cmb.1997.4.177","article-title":"On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies","volume":"4","author":"ZHANG","year":"1997","journal-title":"J. Comput. Biol."},{"key":"ref_233","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1093\/bioinformatics\/17.9.821","article-title":"A simple algorithm to infer gene duplication and speciation events on a gene tree","volume":"17","author":"Zmasek","year":"2001","journal-title":"Bioinformatics"},{"key":"ref_234","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","article-title":"Fast Algorithms for Finding Nearest Common Ancestors","volume":"13","author":"Harel","year":"1984","journal-title":"SIAM J. Comput."},{"key":"ref_235","doi-asserted-by":"crossref","unstructured":"Bender, M.A., and Farach-Colton, M. (2000). The LCA Problem Revisited. LATIN 2000: Theoretical Informatics, Springer.","DOI":"10.1007\/10719839_9"},{"key":"ref_236","doi-asserted-by":"crossref","unstructured":"Chang, W.C., and Eulenstein, O. (2006). Reconciling Gene Trees with Apparent Polytomies. Computing and Combinatorics, Springer.","DOI":"10.1007\/11809678_26"},{"key":"ref_237","doi-asserted-by":"crossref","unstructured":"Lafond, M., Swenson, K.M., and El-Mabrouk, N. (2012). An Optimal Reconciliation Algorithm for Gene Trees with Polytomies. Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/978-3-642-33122-0_9"},{"key":"ref_238","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1109\/TCBB.2010.14","article-title":"Simultaneous Identification of Duplications and Lateral Gene Transfers","volume":"8","author":"Tofigh","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_239","doi-asserted-by":"crossref","unstructured":"Doyon, J.P., Scornavacca, C., Gorbunov, K.Y., Sz\u00f6ll\u0151si, G.J., Ranwez, V., and Berry, V. (2010). An Efficient Algorithm for Gene\/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers. Comparative Genomics, Springer.","DOI":"10.1007\/978-3-642-16181-0_9"},{"key":"ref_240","doi-asserted-by":"crossref","first-page":"i283","DOI":"10.1093\/bioinformatics\/bts225","article-title":"Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss","volume":"28","author":"Bansal","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_241","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1089\/cmb.2009.0240","article-title":"The Cophylogeny Reconstruction Problem Is NP-Complete","volume":"18","author":"Ovadia","year":"2011","journal-title":"J. Comput. Biol."},{"key":"ref_242","doi-asserted-by":"crossref","unstructured":"Hallett, M.T., and Lagergren, J. (2001, January 22\u201325). Efficient Algorithms for Lateral Gene Transfer Problems. Proceedings of the Fifth Annual International Conference on Computational Biology (RECOMB \u201901), Montreal, QC, Canada.","DOI":"10.1145\/369133.369188"},{"key":"ref_243","doi-asserted-by":"crossref","first-page":"1981","DOI":"10.1007\/s00285-019-01331-w","article-title":"Gene tree species tree reconciliation with gene conversion","volume":"78","author":"Tannier","year":"2019","journal-title":"J. Math. Biol."},{"key":"ref_244","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1007\/s10878-019-00396-z","article-title":"Gene tree reconciliation including transfers with replacement is NP-hard and FPT","volume":"38","author":"Tannier","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_245","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1080\/10635150500354928","article-title":"Inferring Phylogeny Despite Incomplete Lineage Sorting","volume":"55","author":"Maddison","year":"2006","journal-title":"Syst. Biol."},{"key":"ref_246","doi-asserted-by":"crossref","first-page":"6:1","DOI":"10.1186\/s13015-017-0098-8","article-title":"On the computational complexity of the maximum parsimony reconciliation problem in the duplication-loss-coalescence model","volume":"12","author":"Bork","year":"2017","journal-title":"Algorithms Mol. Biol."},{"key":"ref_247","doi-asserted-by":"crossref","first-page":"i409","DOI":"10.1093\/bioinformatics\/bts386","article-title":"Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees","volume":"28","author":"Stolzer","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_248","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jtbi.2017.08.008","article-title":"Inferring incomplete lineage sorting, duplications, transfers and losses with reconciliations","volume":"432","author":"Ranwez","year":"2017","journal-title":"J. Theor. Biol."},{"key":"ref_249","doi-asserted-by":"crossref","unstructured":"To, T.H., and Scornavacca, C. (2015). Efficient algorithms for reconciling gene trees and species networks via duplication and loss events. BMC Genom., 16.","DOI":"10.1186\/1471-2164-16-S10-S6"},{"key":"ref_250","doi-asserted-by":"crossref","first-page":"2503","DOI":"10.1098\/rstb.2011.0014","article-title":"The genome as a life-history character: why rate of molecular evolution varies between mammal species","volume":"366","author":"Bromham","year":"2011","journal-title":"Philos. Trans. R. Soc. B Biol. Sci."},{"key":"ref_251","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","article-title":"Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology","volume":"20","author":"Fitch","year":"1971","journal-title":"Syst. Biol."},{"key":"ref_252","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/TCBB.2008.119","article-title":"Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic","volume":"6","author":"Jin","year":"2009","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_253","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/140959948","article-title":"On Computing the Maximum Parsimony Score of a Phylogenetic Network","volume":"29","author":"Fischer","year":"2015","journal-title":"SIAM J. Discret. Math."},{"key":"ref_254","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.tcs.2008.04.019","article-title":"Seeing the trees and their branches in the network is hard","volume":"401","author":"Kanj","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_255","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.dam.2017.07.015","article-title":"Solving the tree containment problem in linear time for nearly stable phylogenetic networks","volume":"246","author":"Gambette","year":"2018","journal-title":"Discret. Appl. Math."},{"key":"ref_256","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Kumpijit, T., and Putwattana, A. (2015, January 22\u201324). A faster algorithm for the tree containment problem for binary nearly stable phylogenetic networks. Proceedings of the 2015 12th International Joint Conference on Computer Science and Software Engineering (JCSSE), Songkhla, Thailand.","DOI":"10.1109\/JCSSE.2015.7219820"},{"key":"ref_257","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/j.aam.2016.04.004","article-title":"Reticulation-visible networks","volume":"78","author":"Bordewich","year":"2016","journal-title":"Adv. Appl. Math."},{"key":"ref_258","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/j.ic.2016.11.001","article-title":"A decomposition theorem and two algorithms for reticulation-visible networks","volume":"252","author":"Gunawan","year":"2017","journal-title":"Inf. Comput."},{"key":"ref_259","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1016\/j.ipl.2010.07.027","article-title":"Locating a tree in a phylogenetic network","volume":"110","author":"Semple","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_260","doi-asserted-by":"crossref","unstructured":"Gunawan, A.D.M. (2018). Solving the Tree Containment Problem for Reticulation-Visible Networks in Linear Time. Algorithms for Computational Biology, Springer International Publishing.","DOI":"10.1007\/978-3-319-91938-6_3"},{"key":"ref_261","doi-asserted-by":"crossref","unstructured":"Weller, M. (2018, January 9\u201312). Linear-Time Tree Containment in Phylogenetic Networks. Proceedings of the 16th International Conference on Comparative Genomics (RECOMB-CG 2018), Magog-Orford, QC, Canada.","DOI":"10.1007\/978-3-030-00834-5_18"},{"key":"ref_262","doi-asserted-by":"crossref","first-page":"i503","DOI":"10.1093\/bioinformatics\/btw467","article-title":"A program for verification of phylogenetic network models","volume":"32","author":"Gunawan","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_263","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.1007\/s11538-016-0199-4","article-title":"Do Branch Lengths Help to Locate a Tree in a Phylogenetic Network?","volume":"78","author":"Gambette","year":"2016","journal-title":"Bull. Math. Biol."},{"key":"ref_264","unstructured":"Huber, K.T., van Iersel, L., Janssen, R., Jones, M., Moulton, V., Murakami, Y., and Semple, C. (2019). Rooting for phylogenetic networks. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/12\/256\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:39:02Z","timestamp":1760189942000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/12\/256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,1]]},"references-count":264,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["a12120256"],"URL":"https:\/\/doi.org\/10.3390\/a12120256","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,1]]}}}