Protein structure comparison exhibits differences and similarities of proteins and protein families and may help to elucidate protein sequence and structure evolution. Despite many methods to score protein structure similarity with and without flexibility and to align proteins accurately based on their structures, a meaningful evolutionary distance measure and alignment method which models the cost of mutations, insertions and deletions occurring in protein sequences on the structure level is still missing.