LINEAR-TIME MATCHING OF POSITION WEIGHT MATRICES

摘要

Position Weight Matrices are a popular way of representing variable motifs in genomic sequences, and they have been widely used for describing the binding sites of transcriptional proteins. However, the standard implementation of PWM matching, while not inefficient on shorter sequences, is too expensive for wholegenome searches. In this paper we present an algorithm we have developed for efficient matching of PWMs in long target sequences. After the initial pre-processing of the matrix it performs in time linear to the size of the genomic segment.