Automated linear motif discovery from protein interaction network

Abstract

This thesis describes a new problem of automated motif discovery from protein interaction network to circumvent the bottleneck caused by the lack of prior biological knowledge. We propose a motif pair approach which can extract motifs from sparse interaction data and is robust against noise in input data. Pairs of motifs are mined from similar co-occurring subsequences embedded in pairs of interacting sequences and we model the task as a novel double cliques finding problem. As finding clique is NP-Hard, we designed an algorithm (D-STAR) was designed to find the approximate solutions and validated the algorithm on sets of semi-synthetic and real biological data.