Classifying and Counting Linear Phylogenetic Invariants for the Jukes–Cantor Model

Abstract

Linear invariants are useful tools for testing phylogenetic hypotheses from aligned DNA/RNA sequences, particularly when the sites evolve at different rates. Here we give a simple, graph theoretic classification for each phylogenetic tree T, of its associated vector space I(T) of linear invariants under the Jukes-Cantor one-parameter model of nucleotide substitution. We also provide an easily described basis for I(T), and show that if I is a binary (fully resolved) phylogenetic tree with n sequences at its leaves then: dim[I(T)] = 4n-F2n-2 where Fn is the nth Fibonacci number. Our method applies a recently developed Hadamard matrix-based technique to describe elements of I(T) in terms of edge-disjoint packings of subtrees in T, and thereby complements earlier more algebraic treatments.