Balanced randomized tree splitting with applications to evolutionary tree constructions
Given a graph theoretical tree \(T\), a method is presented for splitting \(T\) up into components with a balanced number of leaves with high probability. This method is based on Theorem 1 of the paper, which states the following: If \(T\) has \(n\) leaves, and a sample \(S\) consisting of at least \(2 k \frac{n}{n_0} \log n\) leaves is chosen uniformly at random, \(2 \leq n_0 < n\), \(k \geq 2\), then each of the components of \(T\) less the topological subtree of \(T\) induced by \(S\) contains less than \(n_0\) leaves with probability at least \(1 - n^{-k}\). Two applications to well-known problems arising in the construction of evolutionary trees (i.e. trees whose leaves represent present day species and whose internal nodes represent common ancestors) are given: (1) An experiment determines how three species are related in an evolutionary tree. Using balanced tree splitting it is shown that an evolutionary tree \(T\) with \(n\) species can be determined using experiments in expected time \(O(n d \log n \log \log n)\), where \(d\) is the maximum degree of \(T\). A lower bound on the number of experiments is also given. (2) The maximum agreement subtree problem is considered for binary trees where the maximum number of leaves in the optimum solution is large. In particular, given an input of \(k\) \(n\)-leaf binary trees admitting an agreement subtree on at least \(\beta n\) leaves, \(\beta \in (0.8,1]\), balanced tree splitting is used to construct an agreement subtree whose expected number of leaves is at least \(0.4 \beta n\) in time \(O(k n^{\frac{9}{5}} \log^{\frac{6}{5}} n)\). For the entire collection see [Zbl 0909.00052].
This page was built for publication: Balanced randomized tree splitting with applications to evolutionary tree constructions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4251050)
