**Abstract**.
Perfect phylogeny is a fundamental model for the study of evolution.
Given a set of binary sequences of the same length, perfect
phylogeny is the problem of fitting the sequences as leaves of a
rooted tree such that no site mutates more than once, and site
consistency is the problem of finding a largest subset of sites that
can fit a perfect phylogeny. The site consistency problem is known
to be NP-hard, but polynomial-time solvable if the set of sequences
can be derived on a particular form of phylogenetic network with
recombination, called a galled-tree. In this paper, we introduce the
problem dual to site consistency, called sequence consistency,
provide a linear-time algorithm for site consistency when the set of
sequences can be derived on a galled-tree, and study the
parameterized complexity of both site and sequence consistency.