Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.3
URN: urn:nbn:de:0030-drops-128696
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12869/
Afshar, Ramtin ; Goodrich, Michael T. ; Matias, Pedro ; Osegueda, Martha C.
Reconstructing Biological and Digital Phylogenetic Trees in Parallel
| pdf-format: |
|
Abstract
In this paper, we study the parallel query complexity of reconstructing biological and digital phylogenetic trees from simple queries involving their nodes. This is motivated from computational biology, data protection, and computer security settings, which can be abstracted in terms of two parties, a responder, Alice, who must correctly answer queries of a given type regarding a degree-d tree, T, and a querier, Bob, who issues batches of queries, with each query in a batch being independent of the others, so as to eventually infer the structure of T. We show that a querier can efficiently reconstruct an n-node degree-d tree, T, with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries, including relative-distance queries and path queries. Our results are all asymptotically optimal and improve the asymptotic (sequential) query complexity for one of the problems we study. Moreover, through an experimental analysis using both real-world and synthetic data, we provide empirical evidence that our algorithms provide significant parallel speedups while also improving the total query complexities for the problems we study.
BibTeX - Entry
@InProceedings{afshar_et_al:LIPIcs:2020:12869,
author = {Ramtin Afshar and Michael T. Goodrich and Pedro Matias and Martha C. Osegueda},
title = {{Reconstructing Biological and Digital Phylogenetic Trees in Parallel}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {3:1--3:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12869},
URN = {urn:nbn:de:0030-drops-128696},
doi = {10.4230/LIPIcs.ESA.2020.3},
annote = {Keywords: Tree Reconstruction, Parallel Algorithms, Privacy, Phylogenetic Trees, Data Structures, Hierarchical Clustering}
}
| Keywords: | Tree Reconstruction, Parallel Algorithms, Privacy, Phylogenetic Trees, Data Structures, Hierarchical Clustering | |
| Seminar: | 28th Annual European Symposium on Algorithms (ESA 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 26.08.2020 | |
| Supplementary Material: | The complete source code for our experiments, including the implementation of our algorithms and the algorithms we compared against, is available at https://github.com/UC-Irvine-Theory/ParallelTreeReconstruction. |
