{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T05:08:34Z","timestamp":1773292114635,"version":"3.50.1"},"reference-count":16,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"published-print":{"date-parts":[[2024,1,1]]},"abstract":"<jats:p>\n                    <jats:bold>Due to uncertainty in tumor phylogeny inference from sequencing data, many methods infer multiple, equally plausible phylogenies for the same cancer. To summarize the solution space<\/jats:bold>\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>T<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    <jats:bold>of tumor phylogenies, consensus tree methods seek a single best representative tree<\/jats:bold>\n                    <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    <jats:bold>under a specified pairwise tree distance function. One such distance function is the ancestor\u2013descendant (AD) distance<\/jats:bold>\n                    <jats:italic toggle=\"yes\">\n                      <jats:inline-formula>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                          <mml:mi>d<\/mml:mi>\n                          <mml:mrow>\n                            <mml:mo class=\"MathClass-open\">(<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>T<\/mml:mi>\n                              <mml:mo class=\"MathClass-punc\">,<\/mml:mo>\n                              <mml:mi>T<\/mml:mi>\n                              <mml:mi>\u2032<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo class=\"MathClass-close\">)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:inline-formula>\n                    <\/jats:italic>\n                    <jats:bold>\n                      , which equals the size of the symmetric difference of the transitive closures of the edge sets\n                      <jats:italic toggle=\"yes\">\n                        <jats:inline-formula>\n                          <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                            <mml:mi>E<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mo class=\"MathClass-open\">(<\/mml:mo>\n                              <mml:mrow>\n                                <mml:mi>T<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mo class=\"MathClass-close\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:math>\n                        <\/jats:inline-formula>\n                      <\/jats:italic>\n                      and\n                      <jats:italic toggle=\"yes\">\n                        <jats:inline-formula>\n                          <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                            <mml:mi>E<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mo class=\"MathClass-open\">(<\/mml:mo>\n                              <mml:mrow>\n                                <mml:mi>T<\/mml:mi>\n                                <mml:mi>\u2032<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mo class=\"MathClass-close\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:math>\n                        <\/jats:inline-formula>\n                      <\/jats:italic>\n                      . Here, we show that finding a consensus tree\n                    <\/jats:bold>\n                    <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    <jats:bold>for tumor phylogenies<\/jats:bold>\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>T<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    <jats:bold>\n                      that minimizes the total AD distance\n                      <jats:italic toggle=\"yes\">\n                        <jats:inline-formula>\n                          <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                            <mml:msub>\n                              <mml:mrow>\n                                <mml:mo class=\"MathClass-op\">\u2211<\/mml:mo>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>T<\/mml:mi>\n                                <mml:mo class=\"MathClass-rel\">\u2208<\/mml:mo>\n                                <mml:mi>T<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msub>\n                            <mml:mi>d<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mo class=\"MathClass-open\">(<\/mml:mo>\n                              <mml:mrow>\n                                <mml:mi>S<\/mml:mi>\n                                <mml:mo class=\"MathClass-punc\">,<\/mml:mo>\n                                <mml:mi>T<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mo class=\"MathClass-close\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:math>\n                        <\/jats:inline-formula>\n                      <\/jats:italic>\n                      is NP-hard.\n                    <\/jats:bold>\n                  <\/jats:p>","DOI":"10.1089\/cmb.2023.0262","type":"journal-article","created":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T11:13:11Z","timestamp":1701083591000},"page":"58-70","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Consensus Tree Under the Ancestor\u2013Descendant Distance is NP-Hard"],"prefix":"10.1177","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-9871-7415","authenticated-orcid":false,"given":"Yuanyuan","family":"Qi","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, Illinois, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1468-2407","authenticated-orcid":false,"given":"Mohammed","family":"El-kebir","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, Illinois, USA."},{"name":"Cancer Center at Illinois, University of Illinois Urbana-Champaign, Urbana, Illinois, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2024,1,11]]},"reference":[{"key":"e_1_3_5_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz312"},{"key":"e_1_3_5_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa801"},{"key":"e_1_3_5_4_1","doi-asserted-by":"crossref","unstructured":"Cook SA. The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. 1971; pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_5_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz869"},{"key":"e_1_3_5_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2016.07.004"},{"key":"e_1_3_5_7_1","doi-asserted-by":"crossref","unstructured":"Fu X Schwartz R. Contreedp: A consensus method of tumor trees based on maximum directed partition support problem. In: 2021 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE; 2021; pp. 125\u2013130.","DOI":"10.1109\/BIBM52615.2021.9669279"},{"key":"e_1_3_5_8_1","first-page":"63","article-title":"A consensus approach to infer tumor evolutionary histories","author":"Govek K","year":"2018","unstructured":"Govek K, , Sikes C, , Oesper L. A consensus approach to infer tumor evolutionary histories. BCB, 2018; 63\u201372.","journal-title":"BCB"},{"key":"e_1_3_5_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2020.3029689"},{"key":"e_1_3_5_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btad230"},{"key":"e_1_3_5_11_1","unstructured":"Karp RM. Reducibility among combinatorial problems. In: Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations held March 20\u201322 1972 at the IBM Thomas J. Watson Research Center Yorktown Heights New York and sponsored by the Office of Naval Research Mathematics Program IBM World Trade Corporation and the IBM Research Mathematical Sciences Department. (Miller RE Thatcher JW Bohlinger JD. eds.) Springer US: Boston MA USA; 1972; pp. 85\u2013103."},{"key":"e_1_3_5_12_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-019-0152-9"},{"key":"e_1_3_5_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/genetics\/61.4.893"},{"key":"e_1_3_5_14_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.959840"},{"key":"e_1_3_5_15_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-019-0155-6"},{"key":"e_1_3_5_16_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrg.2016.170"},{"key":"e_1_3_5_17_1","doi-asserted-by":"crossref","unstructured":"Zuckerman D. Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing. 2006; pp. 681\u2013690.","DOI":"10.1145\/1132516.1132612"}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1089\/cmb.2023.0262","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1089\/cmb.2023.0262","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1089\/cmb.2023.0262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T12:43:22Z","timestamp":1773233002000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1089\/cmb.2023.0262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,1]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,1]]}},"alternative-id":["10.1089\/cmb.2023.0262"],"URL":"https:\/\/doi.org\/10.1089\/cmb.2023.0262","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2023.07.17.549375","asserted-by":"object"}]},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,1]]}}}