An invariant Q of a tree T under a k-state Markov model, where a generalized time parameter is identified with the E edges of T, allows us to recognize whether data on N observed species (usually, N DNA sequences, one from each species) can be associated with the N leaves of T in the sense of having been generated on T rather than on any other N-leaf tree. The form of the generalized time parameter is a positive determinant matrix in some semigroup S of Markov matrices. The invariance is with respect to the choice of the set of E matrices in S, one associated with each of the E edges of T. The parametric form of S represents a model of the evolutionary process. In this paper, we apply a general method of finding invariants of a parametrized functional form to find low-degree polynomial invariants for different models. Quadratic invariants are obtained for the Kimura two-parameter model, for a model allowing evolutionary dependence between positions in the sequences and for an asymmetric model that allows for A + T versus G + C asymmetries in DNA base composition. Those invariants are found for trees (unrooted in case of the Kimura model and rooted for the others) with N = 3 or N = 4 terminal vertices. We also find cubic invariants for a ten-parameter model with k = 4 states, for rooted trees with N = 4. In each case, we use implicit function theory to predict the number of algebraically independent invariants and then use this prediction to guide a systematic search for algebraic dependence within the set of invariants produced by our method.