Blog
About

13
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A note on convex characters and Fibonacci numbers

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Given an unrooted, binary phylogenetic tree T on a set of n >= 2 taxa, a closed expression for the number of convex characters on T has been known since 1992, and this is independent of the exact topology of T. Here we prove that this number is equal to the (2n-1)th Fibonacci number. Moreover, we show that the number of convex characters in which each state appears on at least two taxa, is also independent of topology, and equal to the (n-1)th Fibonacci number. We use this insight to give a simple but effective algorithm for the NP-hard "maximum parsimony distance" problem that runs in time \(\Theta( \phi^{n} \cdot \text{poly}(n) )\), where \(\phi \approx 1.618...\) is the golden ratio. Finally, we give an explicit example demonstrating that topological neutrality no longer holds when counting the number of convex characters in which each state appears on at least three taxa.

          Related collections

          Author and article information

          Journal
          2015-08-11
          2016-01-27
          1508.02598

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Custom metadata
          added a number of footnotes concerning classical Fibonaci identities
          q-bio.PE cs.DS math.CO

          Evolutionary Biology, Combinatorics, Data structures & Algorithms

          Comments

          Comment on this article

          Similar content 1,734