SUMMARY: To reveal how the polycomb repressive-deubiquitinase (PR-DUB) complex controls substrate selection specificity, we undertook a detailed computational sequence analysis of its components: additional sex combs like 1 (ASXL1) and BRCA1-associated protein 1 (BAP1) proteins. This led to the discovery of two previously unrecognized domains in ASXL1: a forkhead (winged-helix) DNA-binding domain and a deubiquitinase adaptor domain shared with two regulators of ubiquitin carboxyl-terminal hydrolase 37 (Uch37), namely adhesion regulating molecule 1 (ADRM1) and nuclear factor related to kappaB (NFRKB). Our analysis demonstrates a common ancestry for BAP1 and Uch37 regulators in PR-DUB, INO80 chromatin remodelling and proteosome complexes. CONTACT: luis.sanchezpulido@dpag.ox.ac.uk SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.