{"doi":"10.1186/s12859-019-3203-9","title":"An efficient exact algorithm for computing all pairwise distances between reconciliations in the duplication-transfer-loss model","abstract":"<jats:title>Abstract</jats:title><jats:sec>\n<jats:title>Background</jats:title>\n<jats:p>Maximum parsimony reconciliation in the duplication-transfer-loss model is widely used in studying the evolutionary histories of genes and species and in studying coevolution of parasites and their hosts and pairs of symbionts. While efficient algorithms are known for finding maximum parsimony reconciliations, the number of reconciliations can grow exponentially in the size of the trees. An understanding of the space of maximum parsimony reconciliations is necessary to determine whether a single reconciliation can adequately represent the space or whether multiple representative reconciliations are needed.</jats:p>\n</jats:sec><jats:sec>\n<jats:title>Results</jats:title>\n<jats:p>We show that for any instance of the reconciliation problem, the distribution of pairwise distances can be computed exactly by an efficient polynomial-time algorithm with respect to several different distance metrics. We describe the algorithm, analyze its asymptotic worst-case running time, and demonstrate its utility and viability on a large biological dataset.</jats:p>\n</jats:sec><jats:sec>\n<jats:title>Conclusions</jats:title>\n<jats:p>This result provides new insights into the structure of the space of maximum parsimony reconciliations. These insights are likely to be useful in the wide range of applications that employ reconciliation methods.</jats:p>\n</jats:sec>","journal":"BMC Bioinformatics","year":2019,"id":44305,"datarank":0.4936746096997805,"base_score":2.5649493574615367,"endowment":2.5649493574615367,"self_citation_contribution":0.38474240361923057,"citation_network_contribution":0.10893220608054993,"self_endowment_contribution":0.38474240361923057,"citer_contribution":0.10893220608054993,"corpus_percentile":null,"corpus_rank":null,"citation_count":12,"citer_count":8,"citers_with_citation_signal":4,"citers_with_endowment":4,"datacite_reuse_total":1,"is_dataset":false,"is_dataset_confidence":null,"is_oa":false,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":null,"fair_score":67.5,"fair_percentile":95.5,"algorithm_id":"datarank_citation_only_1hop_v6","ranking_scope":"data_only","authors":[{"id":208807,"name":"Ross Mawhorter","orcid":null,"position":1,"is_corresponding":false},{"id":63068,"name":"Ran Libeskind-Hadas","orcid":"0000-0001-9120-1948","position":2,"is_corresponding":false},{"id":208806,"name":"Santi Santichaivekin","orcid":null,"position":0,"is_corresponding":false}],"reference_count":0,"raw_metadata":{"has_enrichment":true,"base_score":2.5649493574615367,"endowment":2.5649493574615367,"datacite_reuse_total":1,"file_count":0,"downloads":0,"views":0,"has_version_chain":false,"is_dataset":false,"is_oa":false,"pmid":"31842734","pmcid":"PMC6915856","openalex_id":"https://openalex.org/W2996572512","authors":[],"funders":[],"total_grants":0,"fwci":0.7693,"citation_percentile":0.71856007,"influential_citations":1,"citation_trend":[{"year":2019,"count":1},{"year":2020,"count":1},{"year":2021,"count":1},{"year":2022,"count":6},{"year":2023,"count":1},{"year":2024,"count":1},{"year":2025,"count":1}],"oa_status":"gold","license":"cc-by","oa_locations":[{"url":"https://bmcbioinformatics.biomedcentral.com/track/pdf/10.1186/s12859-019-3203-9","host_type":"journal"},{"url":"https://bmcbioinformatics.biomedcentral.com/track/pdf/10.1186/s12859-019-3203-9","host_type":"GOLD"},{"url":"https://bmcbioinformatics.biomedcentral.com/track/pdf/10.1186/s12859-019-3203-9","host_type":"publisher"},{"url":"http://link.springer.com/content/pdf/10.1186/s12859-019-3203-9.pdf","host_type":"publisher"},{"url":"http://link.springer.com/article/10.1186/s12859-019-3203-9/fulltext.html","host_type":"publisher"},{"url":"https://doi.org/10.1186/s12859-019-3203-9","host_type":"journal"},{"url":"https://pubmed.ncbi.nlm.nih.gov/31842734","host_type":"repository"},{"url":"https://doaj.org/article/a9bdf3b932af4daf8eeb4e7ff7c8e756","host_type":"repository"},{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/6915856","host_type":"repository"},{"url":"https://europepmc.org/articles/PMC6915856","host_type":"Europe_PMC"},{"url":"https://europepmc.org/articles/PMC6915856?pdf=render","host_type":"Europe_PMC"}],"fields_of_study":["Genomics and Phylogenetic Studies","Evolution and Genetic Dynamics","Genome Rearrangement Algorithms","Computer Science","Medicine","Biology","Algorithms","Evolution, Molecular","Gene Duplication","Models, Genetic","Time Factors"],"mesh_terms":["Algorithms","Models, Genetic","Time Factors","Evolution, Molecular","Gene Duplication"],"keywords":["Pairwise comparison","Computer science","Maximum parsimony","Algorithm","Time complexity","Range (aeronautics)","Phylogenetic tree","Transfer (computing)","Theoretical computer science","Artificial intelligence","Biology","Gene","Parallel computing","Phylogenetic Trees","Duplication-transfer-loss Model","Maximum Parsimony Reconciliation"],"sdg_mappings":[{"sdg_number":0,"sdg_label":"Reduced inequalities"}],"linked_datasets":[{"doi":"10.4230/lipics.wabi.2021.3","title":"Making Sense of a Cophylogeny Output: Efficient Listing of Representative Reconciliations","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","resource_type":"ConferencePaper"}],"clinical_trials":[],"software_tools":[],"database_accessions":[],"source":"live","citation_network_status":"fetched"},"created_at":"2026-06-19T22:31:00.719232Z","pmid":null,"pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"fair_f":100.0,"fair_a":70.0,"fair_i":50.0,"fair_r":50.0,"fair_zscore":null,"fair_rationale":{"fair_score":67.5,"has_llm":false,"dimensions":{"F":{"name":"Findable","score":100.0,"criteria":[{"key":"f_has_doi","label":"Has a persistent DOI","kind":"deterministic","weight":1.0,"fraction":1.0,"signal":"DOI present","rationale":null},{"key":"f_repository_presence","label":"Indexed in repositories / literature DBs","kind":"deterministic","weight":1.0,"fraction":1.0,"signal":"datacite=1, pmcid=True, pmid=True","rationale":null},{"key":"f_persistent_ids","label":"Resolvable scholarly identifiers (OpenAlex)","kind":"deterministic","weight":0.5,"fraction":1.0,"signal":"OpenAlex id present","rationale":null}]},"A":{"name":"Accessible","score":70.0,"criteria":[{"key":"a_open_access","label":"Open Access / files deposited","kind":"deterministic","weight":1.5,"fraction":0.5,"signal":"files/OA location present but not flagged OA","rationale":null},{"key":"a_retrievable","label":"Free full text retrievable","kind":"deterministic","weight":1.0,"fraction":1.0,"signal":"11 OA location(s)","rationale":null}]},"I":{"name":"Interoperable","score":50.0,"criteria":[{"key":"i_linked_data","label":"Linked datasets / DataCite relations","kind":"deterministic","weight":1.0,"fraction":1.0,"signal":"linked_datasets=1, datacite=1","rationale":null},{"key":"i_standard_ids","label":"References data via standard accessions","kind":"deterministic","weight":1.0,"fraction":0.0,"signal":"accessions=0, trials=0","rationale":null}]},"R":{"name":"Reusable","score":50.0,"criteria":[{"key":"r_license","label":"Clear, open reuse license","kind":"deterministic","weight":1.5,"fraction":1.0,"signal":"open license (cc-by)","rationale":null},{"key":"r_downloads","label":"Demonstrated reuse (downloads)","kind":"deterministic","weight":0.5,"fraction":0.0,"signal":"downloads=0","rationale":null},{"key":"r_version","label":"Versioned / maintained","kind":"deterministic","weight":0.5,"fraction":0.0,"signal":"no version chain","rationale":null},{"key":"r_dataset","label":"Classified as a data resource","kind":"deterministic","weight":0.5,"fraction":0.0,"signal":"not a dataset","rationale":null}]}},"suggestions":["Reference data using standard accessions (e.g. GEO, PDB, ClinicalTrials.gov).","Maintain explicit versioning for the dataset.","Make the paper/data Open Access or deposit the files in an open repository."],"model":null,"agent_version":"fair_agent_v3","fulltext_source":"epmc_xml"},"fair_model":null,"fair_agent_version":"fair_agent_v3","fair_fulltext_source":"epmc_xml","fair_has_llm":false,"fair_computed_at":"2026-06-26T07:17:35.933820Z","clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}