The reconstruction of phylogenetic trees is one of the central challenges in evolutionary biology. Costly algorithms cannot cope with the continuous growth of potential datasets, and heuristic strategies are universally adopted to curb the increased computational burden. Here we propose alternative methods of input reduction founded on the precise mathematical definition of the maximum parsimony criterion and on the notion of conservation of biochemical properties of the molecules and the genes which encode them. We thus extend the as of yet limited existing simplification rules with exact and highly efficient methods to detect and treat parsimoniously related components in the alignment. For this, a generalized framework for heterogeneously modeled parsimony is introduced.