{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/105698"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/105698","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Computing Robinson-Foulds supertree for two trees","abstract":"Made available in DSpace on 2019-11-26T20:35:09Z (GMT). No. of bitstreams: 2 YU-THESIS-2019.pdf: 720940 bytes, checksum: 98f79d5c66de551f7b969ae6400fe54f (MD5) LICENSE.txt: 4205 bytes, checksum: 82c2b9e463c4f1a6ca91c6e1f16d7416 (MD5) Previous issue date: 2019-07-15","abstract_html":"Made available in DSpace on 2019-11-26T20:35:09Z (GMT). No. of bitstreams: 2 YU-THESIS-2019.pdf: 720940 bytes, checksum: 98f79d5c66de551f7b969ae6400fe54f (MD5) LICENSE.txt: 4205 bytes, checksum: 82c2b9e463c4f1a6ca91c6e1f16d7416 (MD5) Previous issue date: 2019-07-15","abstract_has_math":false,"creators":["Yu, Xilin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Warnow, Tandy"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-11-26T20:35:09Z","date_published":"2019-11-26T20:35:09Z","updated_at":"2026-07-22T22:24:44Z","subjects":["Phylogeny estimation","Supertree problem","Robinson-Foulds Supertree","Polynomial time algorithm","NP-hardness","Greedy heuristic","Divide-and-conquer"],"languages":["en"],"rights":["This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/105698","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Warnow, Tandy"]},{"key":"dc:creator","label":"Author","values":["Yu, Xilin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-11-26T20:35:09Z","2019-07-15","2019-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Phylogeny estimation","Supertree problem","Robinson-Foulds Supertree","Polynomial time algorithm","NP-hardness","Greedy heuristic","Divide-and-conquer"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/105698"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Made available in DSpace on 2019-11-26T20:35:09Z (GMT). No. of bitstreams: 2 YU-THESIS-2019.pdf: 720940 bytes, checksum: 98f79d5c66de551f7b969ae6400fe54f (MD5) LICENSE.txt: 4205 bytes, checksum: 82c2b9e463c4f1a6ca91c6e1f16d7416 (MD5) Previous issue date: 2019-07-15","Supertree problems are important in phylogeny estimation. Supertree construction takes in a set of input trees on subsets of species and aims to find a supertree containing all species subjective to some combinatorial or statistical criterion. As such, it can be used to combine trees estimated by different research projects, or to construct species trees from gene trees that may not contain all species, or to serve a part in divide-and-conquer pipelines that improve the scalability of large scale phylogeny estimation. Yet the most promising supertree methods, such as the popular Robinson-Foulds Supertree (RFS) methods, not only cannot guarantee an optimal solution but also are computationally intensive by themselves, as they are heuristics for NP-hard optimization problems. We present the first polynomial time algorithm to exactly solve the RFS problem on two binary input trees, and prove that finding the Robinson-Foulds Supertree of three input trees is NP-hard. We present GreedyRFS, a greedy heuristic for the Robinson-Foulds Supertree problem that operates by using our exact algorithm for RFS on pairs of trees, until all the trees are merged into a single supertree. Our experiments show that GreedyRFS has better accuracy than FastRFS, the leading heuristic for RFS, when the number of input trees is small, which is the natural case for use within divide-and-conquer pipelines.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Xilin Yu, accepted the attached license on 2019-07-15 at 15:53.","The student, Xilin Yu, submitted this Thesis for approval on 2019-07-15 at 15:59.","This Thesis was approved for publication on 2019-07-15 at 16:49.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14324 on 2019-11-26 at 12:53:42"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Computing Robinson-Foulds supertree for two trees"]}]}],"canonical_facts":{"dc:contributor":["Warnow, Tandy"],"dc:creator":["Yu, Xilin"],"dc:date":["2019-11-26T20:35:09Z","2019-07-15","2019-08"],"dc:description":["Made available in DSpace on 2019-11-26T20:35:09Z (GMT). No. of bitstreams: 2 YU-THESIS-2019.pdf: 720940 bytes, checksum: 98f79d5c66de551f7b969ae6400fe54f (MD5) LICENSE.txt: 4205 bytes, checksum: 82c2b9e463c4f1a6ca91c6e1f16d7416 (MD5) Previous issue date: 2019-07-15","Supertree problems are important in phylogeny estimation. Supertree construction takes in a set of input trees on subsets of species and aims to find a supertree containing all species subjective to some combinatorial or statistical criterion. As such, it can be used to combine trees estimated by different research projects, or to construct species trees from gene trees that may not contain all species, or to serve a part in divide-and-conquer pipelines that improve the scalability of large scale phylogeny estimation. Yet the most promising supertree methods, such as the popular Robinson-Foulds Supertree (RFS) methods, not only cannot guarantee an optimal solution but also are computationally intensive by themselves, as they are heuristics for NP-hard optimization problems. We present the first polynomial time algorithm to exactly solve the RFS problem on two binary input trees, and prove that finding the Robinson-Foulds Supertree of three input trees is NP-hard. We present GreedyRFS, a greedy heuristic for the Robinson-Foulds Supertree problem that operates by using our exact algorithm for RFS on pairs of trees, until all the trees are merged into a single supertree. Our experiments show that GreedyRFS has better accuracy than FastRFS, the leading heuristic for RFS, when the number of input trees is small, which is the natural case for use within divide-and-conquer pipelines.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Xilin Yu, accepted the attached license on 2019-07-15 at 15:53.","The student, Xilin Yu, submitted this Thesis for approval on 2019-07-15 at 15:59.","This Thesis was approved for publication on 2019-07-15 at 16:49.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14324 on 2019-11-26 at 12:53:42"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/105698"],"dc:language":["en"],"dc:rights":["This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/."],"dc:subject":["Phylogeny estimation","Supertree problem","Robinson-Foulds Supertree","Polynomial time algorithm","NP-hardness","Greedy heuristic","Divide-and-conquer"],"dc:title":["Computing Robinson-Foulds supertree for two trees"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:44Z"}