Conservation of Combinatorial Structures in Evolution Scenarios