{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:35Z","timestamp":1740144515466,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005721","name":"Universit\u00e4t Bielefeld","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>A classical problem in comparative genomics is to compute the rearrangement distance, that is the minimum number of large-scale rearrangements required to transform a given genome into another given genome. The traditional approaches in this area are <jats:italic>family-based<\/jats:italic>, i.e., require the classification of DNA fragments of both genomes into <jats:italic>families<\/jats:italic>. Furthermore, the most elementary family-based models, which are able to compute distances in polynomial time, restrict the families to occur at most once in each genome. In contrast, the distance computation in models that allow multifamilies (i.e., families with multiple occurrences) is NP-hard. Very recently, Bohnenk\u00e4mper et al. (J Comput Biol 28:410\u2013431, 2021) proposed an ILP formulation for computing the genomic distance of genomes with multifamilies, allowing structural rearrangements, represented by the generic <jats:italic>double cut and join<\/jats:italic> (DCJ) operation, and content-modifying <jats:italic>insertions<\/jats:italic> and <jats:italic>deletions<\/jats:italic> of DNA segments. This ILP is very efficient, but must maximize a matching of the genes in each multifamily, in order to prevent the <jats:italic>free lunch<\/jats:italic> artifact that would otherwise let empty or almost empty matchings give smaller distances.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>In this paper, we adopt the alternative <jats:italic>family-free<\/jats:italic> setting that, instead of family classification, simply uses the <jats:italic>pairwise similarities<\/jats:italic> between DNA fragments of both genomes to compute their rearrangement distance. We adapted the ILP mentioned above and developed a model in which pairwise similarities are used to assign weights to both matched and unmatched genes, so that an optimal solution does not necessarily maximize the matching. Our model then results in a <jats:italic>natural family-free genomic distance<\/jats:italic>, that takes into consideration all given genes, without prior classification into families, and has a search space composed of matchings of any size. In spite of its bigger search space, our ILP seems to be boosted by a reduction of the number of co-optimal solutions due to the weights. Indeed, it converged faster than the original one by Bohnenk\u00e4mper et al. for instances with the same number of multiple connections. We can handle not only bacterial genomes, but also fungi and insects, or sets of chromosomes of mammals and plants. In a comparison study of six fruit fly genomes, we obtained accurate results.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-021-00183-8","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T12:03:21Z","timestamp":1620648201000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Natural family-free genomic distance"],"prefix":"10.1186","volume":"16","author":[{"given":"Diego P.","family":"Rubert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F\u00e1bio V.","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4092-2646","authenticated-orcid":false,"given":"Mar\u00edlia D. V.","family":"Braga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"key":"183_CR1","doi-asserted-by":"crossref","unstructured":"Sankoff D. Edit distance for genome comparison based on non-local operations. In: Proceedings of the CPM lecture notes in computer science, vol. 644; 1992. p. 121\u201335.","DOI":"10.1007\/3-540-56024-6_10"},{"key":"183_CR2","doi-asserted-by":"crossref","unstructured":"Bergeron A, Mixtacki J, Stoye J. A unifying view of genome rearrangements. In: Proceedings of WABI lecture notes in bioinformatics, vol. 4175; 2006. p. 163\u201373.","DOI":"10.1007\/11851561_16"},{"key":"183_CR3","unstructured":"Hannenhalli S, Pevzner PA. Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proceedings of FOCS; 1995. p. 581\u201392."},{"issue":"16","key":"183_CR4","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"},{"issue":"10","key":"183_CR5","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.1089\/cmb.2009.0092","volume":"16","author":"S Yancopoulos","year":"2009","unstructured":"Yancopoulos S, Friedberg R. DCJ path formulation for genome transformations which include insertions, deletions, and duplications. J Comput Biol. 2009;16(10):1311\u201338.","journal-title":"J Comput Biol"},{"issue":"9","key":"183_CR6","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1089\/cmb.2011.0118","volume":"18","author":"MDV Braga","year":"2011","unstructured":"Braga MDV, Willing E, Stoye J. Double cut and join with insertions and deletions. J Comput Biol. 2011;18(9):1167\u201384.","journal-title":"J Comput Biol"},{"issue":"11","key":"183_CR7","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"15","author":"D Sankoff","year":"1999","unstructured":"Sankoff D. Genome rearrangement with gene families. Bioinformatics. 1999;15(11):909\u201317.","journal-title":"Bioinformatics"},{"key":"183_CR8","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-94-011-4309-7_19","volume-title":"Comparative genomics","author":"D Bryant","year":"2000","unstructured":"Bryant D. The complexity of calculating exemplar distances. In: Sankoff D, Nadeau JH, editors. Comparative genomics. Dordrecht: Springer; 2000. p. 207\u201311."},{"issue":"6","key":"183_CR9","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/TCBB.2012.144","volume":"10","author":"L Bulteau","year":"2013","unstructured":"Bulteau L, Jiang M. Inapproximability of (1,2)-exemplar distance. IEEE ACM Trans Comput Biol Bioinf. 2013;10(6):1384\u201390.","journal-title":"IEEE ACM Trans Comput Biol Bioinf"},{"issue":"1","key":"183_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.7155\/jgaa.00175","volume":"13","author":"S Angibaud","year":"2009","unstructured":"Angibaud S, Fertin G, Rusu I, Th\u00e9venin A, Vialette S. On the approximability of comparing genomes with duplicates. J Graph Algorithm Appl. 2009;13(1):19\u201353.","journal-title":"J Graph Algorithm Appl"},{"issue":"3","key":"183_CR11","first-page":"1","volume":"12","author":"DP Rubert","year":"2017","unstructured":"Rubert DP, Feij\u00e3o P, Braga MDV, Stoye J, Martinez FV. Approximating the DCJ distance of balanced genomes in linear time. Algorithm Mol Biol. 2017;12(3):1\u201313.","journal-title":"Algorithm Mol Biol"},{"issue":"5","key":"183_CR12","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 B. 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":"Suppl 19","key":"183_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1471-2105-13-S19-S3","volume":"13","author":"D Doerr","year":"2012","unstructured":"Doerr D, Th\u00e9venin A, Stoye J. Gene family assignment-free comparative genomics. BMC Bioinf. 2012;13(Suppl 19):3.","journal-title":"BMC Bioinf"},{"key":"183_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-1-4471-5298-9_13","volume-title":"Models and algorithms for genome evolution","author":"MDV Braga","year":"2013","unstructured":"Braga MDV, Chauve C, Doerr D, Jahn K, Stoye J, Th\u00e9venin A, Wittler R. The potential of family-free genome comparison, Chap. 3. In: Chauve C, El-Mabrouk N, Tannier E, editors. Models and algorithms for genome evolution. London: Springer; 2013. p. 287\u2013307."},{"issue":"10","key":"183_CR15","first-page":"1","volume":"13","author":"FV Martinez","year":"2015","unstructured":"Martinez FV, Feijao P, Braga MDV, Stoye J. On the family-free DCJ distance and similarity. Algorithm Mol Biol. 2015;13(10):1\u201310.","journal-title":"Algorithm Mol Biol"},{"issue":"4","key":"183_CR16","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 MDV, 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":"3","key":"183_CR17","first-page":"1","volume":"172","author":"DP Rubert","year":"2020","unstructured":"Rubert DP, Martinez FV, Braga MDV. Natural family-free genomic distance. Leibniz Int Proc Inf (LIPIcs). 2020;172(3):1\u201323.","journal-title":"Leibniz Int Proc Inf (LIPIcs)"},{"issue":"Suppl 9","key":"183_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/1471-2105-12-S9-S13","volume":"12","author":"MDV Braga","year":"2011","unstructured":"Braga MDV, Machado R, Ribeiro LC, Stoye J. On the weight of indels in genomic distances. BMC Bioinf. 2011;12(Suppl 9):13.","journal-title":"BMC Bioinf"},{"key":"183_CR19","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-1-4939-7463-4_12","volume-title":"Comparative genomics: methods and protocols","author":"D Doerr","year":"2018","unstructured":"Doerr D, Feij\u00e3o P, Stoye J. Family-free genome comparison. In: Setubal JC, Stoye J, Stadler PF, editors. Comparative genomics: methods and protocols. New York: Springer; 2018. p. 331\u201342."},{"issue":"4","key":"183_CR20","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1093\/molbev\/msr268","volume":"29","author":"DA Dalquen","year":"2012","unstructured":"Dalquen DA, Anisimova M, Gonnet GH, Dessimoz C. ALF\u2014a simulation framework for genome evolution. Mol Biol Evol. 2012;29(4):1115.","journal-title":"Mol Biol Evol"},{"key":"183_CR21","doi-asserted-by":"publisher","first-page":"2185","DOI":"10.1126\/science.287.5461.2185","volume":"287","author":"MD Adams","year":"2000","unstructured":"Adams MD, Celniker SE, Holt RA, et al. The genome sequence of Drosophila melanogaster. Science. 2000;287:2185\u201395.","journal-title":"Science"},{"key":"183_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1101\/gr.3059305","volume":"15","author":"S Richards","year":"2005","unstructured":"Richards S, Liu Y, Bettencourt BR, et al. Comparative genome sequencing of Drosophila pseudoobscura: chromosomal, gene, and cis-element evolution. Genome Res. 2005;15:1\u201318.","journal-title":"Genome Res"},{"key":"183_CR23","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1038\/nature06341","volume":"450","author":"AG Clark","year":"2007","unstructured":"Clark AG, Eisen MB, Smith DR, et al. Evolution of genes and genomes on the Drosophila phylogeny. Nature. 2007;450:203\u201318.","journal-title":"Nature"},{"issue":"6","key":"183_CR24","doi-asserted-by":"publisher","first-page":"e1005331","DOI":"10.1371\/journal.pgen.1005331","volume":"11","author":"Q Zhou","year":"2015","unstructured":"Zhou Q, Bachtrog D. Ancestral chromatin configuration constrains chromatin evolution on differentiating sex chromosomes in Drosophila. PLoS Genet. 2015;11(6):e1005331.","journal-title":"PLoS Genet"},{"issue":"7","key":"183_CR25","doi-asserted-by":"publisher","first-page":"1152","DOI":"10.1101\/gr.243212.118","volume":"29","author":"AM Altenhoff","year":"2019","unstructured":"Altenhoff AM, Levy J, Zarowiecki M, Tomiczek B, Vesztrocy AW, Dalquen DA, M\u00fcller S, Telford MJ, Glover NM, Dylus D, et al. OMA standalone: orthology inference among public and custom genomes and transcriptomes. Genome Res. 2019;29(7):1152\u201363.","journal-title":"Genome Res"},{"issue":"D1","key":"183_CR26","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1093\/nar\/gkaa1026","volume":"49","author":"A Larkin","year":"2020","unstructured":"Larkin A, Marygold SJ, Antonazzo G, Attrill H, dos Santos G, Garapati PV, Goodman JL, Gramates LS, Millburn G, Strelets VB, Tabone CJ, Thurmond J. FlyBase Consortium: FlyBase: updates to the Drosophila melanogaster knowledge base. Nucleic Acids Res. 2020;49(D1):899\u2013907.","journal-title":"Nucleic Acids Res"},{"issue":"4","key":"183_CR27","first-page":"406","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou N, Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 1987;4(4):406\u201325.","journal-title":"Mol Biol Evol"},{"issue":"6","key":"183_CR28","doi-asserted-by":"publisher","first-page":"1547","DOI":"10.1093\/molbev\/msy096","volume":"35","author":"S Kumar","year":"2018","unstructured":"Kumar S, Stecher G, Li M, Knyaz C, Tamura K. MEGA X: molecular evolutionary genetics analysis across computing platforms. Mol Biol Evol. 2018;35(6):1547\u20139.","journal-title":"Mol Biol Evol"},{"issue":"7","key":"183_CR29","doi-asserted-by":"publisher","first-page":"1812","DOI":"10.1093\/molbev\/msx116","volume":"34","author":"S Kumar","year":"2017","unstructured":"Kumar S, Stecher G, Suleski M, Hedges SB. Timetree: a resource for timelines, timetrees, and divergence times. Mol Biol Evol. 2017;34(7):1812\u20139.","journal-title":"Mol Biol Evol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00183-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00183-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00183-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T04:22:04Z","timestamp":1620706924000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00183-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,10]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["183"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00183-8","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2021,5,10]]},"assertion":[{"value":"1 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"4"}}