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.