{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:24:44Z","timestamp":1772166284155,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T00:00:00Z","timestamp":1695945600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T00:00:00Z","timestamp":1695945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["956229"],"award-info":[{"award-number":["956229"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["1U01HG010973"],"award-info":[{"award-number":["1U01HG010973"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100014690","name":"Ministerium f\u00fcr Kultur und Wissenschaft des Landes Nordrhein-Westfalen","doi-asserted-by":"publisher","award":["PROFILNRW-2020-107-A"],"award-info":[{"award-number":["PROFILNRW-2020-107-A"]}],"id":[{"id":"10.13039\/501100014690","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Universit\u00e4tsklinikum D\u00fcsseldorf. Anstalt \u00f6ffentlichen Rechts"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Homologous recombination between the maternal and paternal copies of a chromosome is a key mechanism for human inheritance and shapes population genetic properties of our species. However, a similar mechanism can also act between different copies of the same sequence, then called\n                    <jats:italic>non-allelic homologous recombination (NAHR)<\/jats:italic>\n                    . This process can result in genomic rearrangements\u2014including deletion, duplication, and inversion\u2014and is underlying many genomic disorders. Despite its importance for genome evolution and disease, there is a lack of computational models to study genomic loci prone to NAHR. In this work, we propose such a computational model, providing a unified framework for both (allelic) homologous recombination and NAHR. Our model represents a set of genomes as a graph, where haplotypes correspond to walks through this graph. We formulate two founder set problems under our recombination model, provide flow-based algorithms for their solution, describe exact methods to characterize the number of recombinations, and demonstrate scalability to problem instances arising in practice.\n                  <\/jats:p>","DOI":"10.1186\/s13015-023-00241-3","type":"journal-article","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T15:01:43Z","timestamp":1695999703000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Constructing founder sets under allelic and non-allelic homologous recombination"],"prefix":"10.1186","volume":"18","author":[{"given":"Konstantinn","family":"Bonnet","sequence":"first","affiliation":[]},{"given":"Tobias","family":"Marschall","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Doerr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,29]]},"reference":[{"key":"241_CR1","doi-asserted-by":"crossref","unstructured":"Ukkonen E. Finding Founder Sequences from a Set of Recombinants. In: 2nd International Workshop on algorithms in bioinformatics (WABI 2002). Algorithms in bioinformatics. Berlin, Heidelberg: Springer Berlin Heidelberg; 2002:277-86.","DOI":"10.1007\/3-540-45784-4_21"},{"issue":"24","key":"241_CR2","doi-asserted-by":"publisher","first-page":"4611","DOI":"10.1093\/bioinformatics\/btab516","volume":"37","author":"T Norri","year":"2021","unstructured":"Norri T, Cazaux B, D\u00f6nges S, Valenzuela D, M\u00e4kinen V. Founder reconstruction enables scalable and seamless pangenomic analysis. Bioinformatics. 2021;37(24):4611\u20139.","journal-title":"Bioinformatics"},{"issue":"9","key":"241_CR3","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1089\/cmb.2008.0065","volume":"15","author":"L Parida","year":"2008","unstructured":"Parida L, Mel\u00e9 M, Calafell F, Bertranpetit J, Consortium G. Estimating the ancestral recombinations graph (ARG) as compatible networks of SNP patterns. J Comput Biol. 2008;15(9):1133\u201353.","journal-title":"J Comput Biol"},{"issue":"15","key":"241_CR4","first-page":"1","volume":"14","author":"KM Swenson","year":"2013","unstructured":"Swenson KM, Guertin P, Desch\u00eanes H, Bergeron A. Reconstructing the modular recombination history of Staphylococcus aureus phages. BMC Bioinform. 2013;14(15):1\u20139.","journal-title":"BMC Bioinform"},{"key":"241_CR5","doi-asserted-by":"crossref","unstructured":"Rastas P, Ukkonen E. Haplotype Inference Via Hierarchical Genotype Parsing. In: Giancarlo R, Hannenhalli S, editors. 7th International Workshop on Algorithms in Bioinformatics (WABI 2007). Algorithms in Bioinformatics. Berlin, Heidelberg: Springer Berlin Heidelberg; 2007:85-97.","DOI":"10.1007\/978-3-540-74126-8_9"},{"key":"241_CR6","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-540-73437-6_17","volume-title":"Combinatorial Pattern Matching","author":"Y Wu","year":"2007","unstructured":"Wu Y, Gusfield D. Improved algorithms for inferring the minimum mosaic of a set of recombinants. In: Ma B, Zhang K, editors. Combinatorial Pattern Matching. Springer, Berlin Heidelberg: Berlin, Heidelberg; 2007. p. 150\u201361."},{"issue":"2","key":"241_CR7","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.cor.2011.03.012","volume":"39","author":"A Roli","year":"2012","unstructured":"Roli A, Benedettini S, St\u00fctzle T, Blum C. Large neighbourhood search algorithms for the founder sequence reconstruction problem. Comput Oper Res. 2012;39(2):213\u201324.","journal-title":"Comput Oper Res"},{"key":"241_CR8","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1007\/978-3-642-02481-8_157","volume-title":"Distributed computing, artificial intelligence, bioinformatics, soft computing, and ambient assisted living","author":"A Roli","year":"2009","unstructured":"Roli A, Blum C, et al. Tabu search for the founder sequence reconstruction problem: a preliminary study. In: Omatu S, Rocha MP, Bravo J, Fern\u00e1ndez F, Corchado E, Bustillo A, et al., editors. Distributed computing, artificial intelligence, bioinformatics, soft computing, and ambient assisted living. Springer, Berlin Heidelberg: Berlin, Heidelberg; 2009. p. 1035\u201342."},{"key":"241_CR9","doi-asserted-by":"crossref","unstructured":"Schwartz R, Clark AG, Istrail S. Methods for inferring block-wise ancestral history from haploid sequences. In: 2nd International Workshop on Algorithms in Bioinformatics (WABI 2002). Algorithms in Bioinformatics. Berlin, Heidelberg: Springer Berlin Heidelberg; 2002:44-59.","DOI":"10.1007\/3-540-45784-4_4"},{"key":"241_CR10","unstructured":"Norri T, Cazaux B, Kosolobov D, M\u00e4kinen V. Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time. In: 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). vol. 113 of Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik; 2018:15:1-15:15."},{"issue":"9","key":"241_CR11","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","volume":"30","author":"R Durbin","year":"2014","unstructured":"Durbin R. Efficient haplotype matching and storage using the positional burrows-wheeler transform (PBWT). Bioinformatics. 2014;30(9):1266\u201372.","journal-title":"Bioinformatics"},{"key":"241_CR12","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1016\/j.ajhg.2021.03.014","volume":"108","author":"X Zhao","year":"2021","unstructured":"Zhao X, Collins RL, Lee WP, Weber AM, Jun Y, Zhu Q, et al. Expectations and blind spots for structural variation detection from long-read assemblies and short-read genome sequencing technologies. Am J Hum Genet. 2021;108:919.","journal-title":"Am J Hum Genet"},{"key":"241_CR13","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1038\/s41576-018-0003-4","volume":"19","author":"FJ Sedlazeck","year":"2018","unstructured":"Sedlazeck FJ, Lee H, Darby CA, Schatz MC. Piercing the dark matter: bioinformatics of long-range sequencing and mapping. Nat Rev Genet. 2018;19:329.","journal-title":"Nat Rev Genet"},{"key":"241_CR14","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1038\/s41587-020-0719-5","volume":"39","author":"D Porubsky","year":"2020","unstructured":"Porubsky D, Ebert P, Audano PA, Vollger MR, Harvey WT, Marijon P, et al. Fully phased human genome assembly without parental data using single-cell strand sequencing and long reads. Nat Biotechnol. 2020;39:302.","journal-title":"Nat Biotechnol"},{"key":"241_CR15","doi-asserted-by":"publisher","DOI":"10.1126\/science.abf7117","author":"P Ebert","year":"2021","unstructured":"Ebert P, Audano PA, Zhu Q, Rodriguez-Martin B, Porubsky D, Bonder MJ, et al. Haplotype-resolved diverse human genomes and integrated analysis of structural variation. Science. 2021. https:\/\/doi.org\/10.1126\/science.abf7117.","journal-title":"Science"},{"issue":"6588","key":"241_CR16","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1126\/science.abj6987","volume":"376","author":"S Nurk","year":"2022","unstructured":"Nurk S, Koren S, Rhie A, Rautiainen M, Bzikadze AV, Mikheenko A, et al. The complete sequence of a human genome. Science. 2022;376(6588):44\u201353.","journal-title":"Science"},{"issue":"7906","key":"241_CR17","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1038\/s41586-022-04601-8","volume":"604","author":"T Wang","year":"2022","unstructured":"Wang T, Antonacci-Fulton L, Howe K, Lawson HA, Lucas JK, Phillippy AM, et al. The human pangenome project: a global resource to map genomic diversity. Nature. 2022;604(7906):437\u201346.","journal-title":"Nature"},{"key":"241_CR18","unstructured":"Liao WW, Asri M, Ebler J, Doerr D, Haukness M, Hickey G, et\u00a0al. A Draft Human Pangenome Reference. bioRxiv. 2022. https:\/\/www.biorxiv.org\/content\/early\/2022\/07\/09\/2022.07.09.499321."},{"issue":"10","key":"241_CR19","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/j.tig.2009.08.002","volume":"25","author":"T Marques-Bonet","year":"2009","unstructured":"Marques-Bonet T, Girirajan S, Eichler EE. The origins and impact of primate segmental duplications. Trends Genet. 2009;25(10):443\u201354.","journal-title":"Trends Genet"},{"issue":"6588","key":"241_CR20","doi-asserted-by":"publisher","first-page":"eabj6965","DOI":"10.1126\/science.abj6965","volume":"376","author":"MR Vollger","year":"2022","unstructured":"Vollger MR, Guitart X, Dishuck PC, Mercuri L, Harvey WT, Gershman A, et al. Segmental duplications and their variation in a complete human genome. Science. 2022;376(6588):eabj6965.","journal-title":"Science"},{"issue":"1","key":"241_CR21","doi-asserted-by":"publisher","first-page":"1784","DOI":"10.1038\/s41467-018-08148-z","volume":"10","author":"MJP Chaisson","year":"2019","unstructured":"Chaisson MJP, Sanders AD, Zhao X, Malhotra A, Porubsky D, Rausch T, et al. Multi-platform discovery of haplotype-resolved structural variation in human genomes. Nat Commun. 2019;10(1):1784.","journal-title":"Nat Commun"},{"key":"241_CR22","doi-asserted-by":"publisher","first-page":"1986","DOI":"10.1016\/j.cell.2022.04.017","volume":"185","author":"D Porubsky","year":"2022","unstructured":"Porubsky D, H\u00f6ps W, Ashraf H, Hsieh P, Rodriguez-Martin B, Yilmaz F, et al. Recurrent inversion polymorphisms in humans associate with genetic instability and genomic disorders. Cell. 2022;185:1986.","journal-title":"Cell"},{"issue":"2","key":"241_CR23","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V Bafna","year":"1996","unstructured":"Bafna V, Pevzner PA. Genome rearrangements and sorting by reversals. SIAM J Comput. 1996;25(2):272\u201389.","journal-title":"SIAM J Comput"},{"key":"241_CR24","doi-asserted-by":"crossref","unstructured":"Bader DA, Moret BM, Yan M. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. In: 1st International Workshop on Algorithms in Bioinformatics (WABI 2001). Algorithms in Bioinformatics. Berlin, Heidelberg: Springer Berlin Heidelberg; 2001:365-76.","DOI":"10.1007\/3-540-44634-6_34"},{"issue":"2","key":"241_CR25","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna V, Pevzner PA. Sorting by transpositions. SIAM J Discret Math. 1998;11(2):224\u201340.","journal-title":"SIAM J Discret Math"},{"key":"241_CR26","unstructured":"Walter MEM, Dias Z, Meidanis J. Reversal and transposition distance of linear chromosomes. In: Proceedings. String Processing and Information Retrieval: A South American Symposium (Cat. No. 98EX207). IEEE; 1998:96-102."},{"key":"241_CR27","doi-asserted-by":"crossref","unstructured":"Dias Z, Meidanis J. Genome Rearrangements Distance by Fusion, Fission, and Transposition is Easy. In: spire. Citeseer; 2001:250-3.","DOI":"10.1109\/SPIRE.2001.989776"},{"issue":"16","key":"241_CR28","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"S Yancopoulos","year":"2005","unstructured":"Yancopoulos S, Attie O, Friedberg R. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics. 2005;21(16):3340\u20136.","journal-title":"Bioinformatics"},{"key":"241_CR29","doi-asserted-by":"crossref","unstructured":"Bergeron A, Mixtacki J, Stoye J. A Unifying View of Genome Rearrangements. In: Bucher P, Moret BME, editors. 6th International Workshop on Algorithms in Bioinformatics (WABI 2006). vol. 4175 of Algorithms in Bioinformatics. Berlin, Heidelberg: Springer Berlin Heidelberg; 2006:163-73.","DOI":"10.1007\/11851561_16"},{"issue":"5","key":"241_CR30","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1089\/cmb.2014.0096","volume":"22","author":"M Shao","year":"2015","unstructured":"Shao M, Lin Y, Moret BME. An exact algorithm to compute the double-cut-and-join distance for genomes with duplicate genes. J Comput Biol. 2015;22(5):425\u201335.","journal-title":"J Comput Biol"},{"issue":"4","key":"241_CR31","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1089\/cmb.2020.0434","volume":"28","author":"L Bohnenk\u00e4mper","year":"2021","unstructured":"Bohnenk\u00e4mper L, Braga MD, Doerr D, Stoye J. Computing the rearrangement distance of natural genomes. J Comput Biol. 2021;28(4):410\u201331.","journal-title":"J Comput Biol"},{"issue":"16","key":"241_CR32","doi-asserted-by":"publisher","first-page":"2476","DOI":"10.1093\/bioinformatics\/btab004","volume":"37","author":"M Rautiainen","year":"2021","unstructured":"Rautiainen M, Marschall T. MBG: minimizer-based sparse de Bruijn graph construction. Bioinformatics. 2021;37(16):2476\u20138.","journal-title":"Bioinformatics"},{"issue":"1","key":"241_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-020-02168-z","volume":"21","author":"H Li","year":"2020","unstructured":"Li H, Feng X, Chu C. The design and construction of reference pangenome graphs with minigraph. Genome Biol. 2020;21(1):1\u201319.","journal-title":"Genome Biol"},{"key":"241_CR34","unstructured":"Garrison E, Guarracino A, Heumos S, Villani F, Bao Z, Tattini L, et\u00a0al.. pggb: the PanGenome Graph Builder; 2023. [Paper submission pending; Online, accessed 27-January-2023]. https:\/\/github.com\/pangenome\/pggb."},{"key":"241_CR35","doi-asserted-by":"crossref","unstructured":"H\u00f6ps W, Rausch T, Ebert P, Human Genome Structural Variation Consortium (HGSVC), Korbel JO, Sedlazeck FJ. Impact and characterization of serial structural variations across humans and great apes; 2023.","DOI":"10.1101\/2023.03.09.531868"},{"key":"241_CR36","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.dam.2016.08.005","volume":"217","author":"G Gutin","year":"2017","unstructured":"Gutin G, Jones M, Sheng B, Wahlstr\u00f6m M, Yeo A. Chinese postman problem on edge-colored multigraphs. Discrete Appl Math. 2017;217:196\u2013202.","journal-title":"Discrete Appl Math"},{"key":"241_CR37","unstructured":"Ahuja RK, Magnanti TL, Orlin JB. Network Flows: Theory, Algorithms, and Applications. 1st ed.; 1993."},{"issue":"4","key":"241_CR38","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/270563.571472","volume":"28","author":"D Gusfield","year":"1997","unstructured":"Gusfield D. Algorithms on stings, trees, and sequences: computer science and computational biology. Acm Sigact News. 1997;28(4):41\u201360.","journal-title":"Acm Sigact News"},{"issue":"3","key":"241_CR39","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen E. On-line construction of suffix trees. Algorithmica. 1995;14(3):249\u201360.","journal-title":"Algorithmica"},{"key":"241_CR40","doi-asserted-by":"crossref","unstructured":"Matsakis ND, Klock\u00a0II FS. The rust language. In: ACM SIGAda Ada Letters. vol. 34(3). ACM; 2014. p. 103-4.","DOI":"10.1145\/2692956.2663188"},{"key":"241_CR41","unstructured":"Gurobi\u00a0Optimization L. Gurobi Optimizer Reference Manual; 2019. http:\/\/www.gurobi.com."},{"key":"241_CR42","unstructured":"Bonnet K, Doerr D. Analysis of the set of founder sequences under a homologous recombination model; 2023. https:\/\/github.com\/marschall-lab\/hrfs."},{"issue":"20","key":"241_CR43","doi-asserted-by":"publisher","first-page":"3350","DOI":"10.1093\/bioinformatics\/btv383","volume":"31","author":"RR Wick","year":"2015","unstructured":"Wick RR, Schultz MB, Zobel J, Holt KE. Bandage: interactive visualization of de novo genome assemblies. Bioinformatics. 2015;31(20):3350\u20132. https:\/\/doi.org\/10.1093\/bioinformatics\/btv383.","journal-title":"Bioinformatics"}],"updated-by":[{"DOI":"10.1186\/s13015-023-00244-0","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T00:00:00Z","timestamp":1701820800000}}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00241-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-023-00241-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00241-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T13:30:48Z","timestamp":1730208648000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-023-00241-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,29]]},"references-count":43,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["241"],"URL":"https:\/\/doi.org\/10.1186\/s13015-023-00241-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2022.05.27.493721","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,29]]},"assertion":[{"value":"31 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2023","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1186\/s13015-023-00244-0","URL":"https:\/\/doi.org\/10.1186\/s13015-023-00244-0","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"15"}}