English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Phylogenetic trees are used to model evolution: leaves are labelled torepresent contemporary species ("taxa") and interior vertices represent extinctancestors. Informally, convex characters are measurements on the contemporaryspecies in which the subset of species (both contemporary and extinct) thatshare a given state, form a connected subtree. Given an unrooted, binaryphylogenetic tree T on a set of n >= 2 taxa, a closed (but fairly opaque)expression for the number of convex characters on T has been known since 1992,and this is independent of the exact topology of T. In this note we prove thatthis number is actually equal to the (2n-1)th Fibonacci number. Next, we defineg_k(T) to be the number of convex characters on T in which each state appearson at least k taxa. We show that, somewhat curiously, g_2(T) is alsoindependent of the topology of T, and is equal to to the (n-1)th Fibonaccinumber. As we demonstrate, this topological neutrality subsequently breaks downfor k >= 3. However, we show that for each fixed k >= 1, g_k(T) can be computedin O(n) time and the set of characters thus counted can be efficiently listedand sampled. We use these insights to give a simple but effective exactalgorithm for the NP-hard maximum parsimony distance problem that runs in time$\Theta( \phi^{n} \cdot n^2 )$, where $\phi \approx 1.618...$ is the goldenratio, and an exact algorithm which computes the tree bisection andreconnection distance (equivalently, a maximum agreement forest) in time$\Theta( \phi^{2n}\cdot \text{poly}(n))$, where $\phi^2 \approx 2.619$.

A note on convex characters, Fibonacci numbers and exponential-time algorithms