Pattern-directed aligned pattern clustering

Functional region identification is of fundamental importance for protein sequences analysis for a protein family. Such knowledge not only provides a better scientific understanding but also assists drug discovery. Domain annotation is one approach but it needs to leverage existing databases. For de novo discovery, motif discovery locates and aligns locally similar sub-sequences and represents them as a position-weight matrix (PWM). However, PWM is a fixed-length model whereas protein functional region size varies. Furthermore, to obtain a PWM, a width range parameter needs to be identified through exhaustive search. Hence, it is computational intensive for large dataset. This paper presents a new method known as Pattern-Directed Aligned Pattern Clustering (PD-APCn) to discover and align residues in conserved protein functional regions. It adopts Aligned Pattern Cluster (APC) as the representation model which allows variable pattern length. It uses patterns with strong support to direct the incremental expansion of the APCs, allowing substitution and frame-shift mutations, until a robust termination condition is reached. The concept of breakpoint gap is introduced to identify uncovered conserved patterns with substitution and frame-shift mutations, where these are often rare mutants. To evaluate the performance of PD-APCn, we conducted experiments on synthetic datasets with different size and noise level. Comparing with the popular motif discovery algorithm MEME, PD-APCn has demonstrated competitive performance throughout the experiments, obtaining a higher recall and Fmeasure with up to 400× significant computational speed up comparing to MEME.