Identifying potential regulatory elements by transcription factor binding site alignment using partial order graphs

Abdollahyan, G. Elgar and F. Smeraldi, in Foundations of Computer Science, vol 29, no. 8, pp 1345-1354, 2018

Abstract

Identification and functional characterization of regulatory elements in the human genome is a challenging task. A sequence feature commonly used to predict regulatory activity is the co-occurrence of transcription factor binding sites (TFBSs) in regulatory regions. In this work, we present a graph-based approach to detect frequently co-occurring TFBSs in evolutionarily conserved non-coding elements (CNEs). We introduce a graph representation of the sequence of TFBSs identified in a CNE that allows us to handle overlapping binding sites. We use a dynamic programming algorithm to align such graphs and determine the relative enrichment of short sequences of TFBSs in the alignments. We evaluate our approach on a set of functionally validated CNEs. Our findings include a regulatory signature composed of co-occurring Pbx-Hox and Meis binding motifs associated with hindbrain enhancer activity.

Keywords:

regulatory element prediction; transcription factor binding site co-occurrence; partial order graphs; dynamic programming.

(Full text)

Backlinks: Publications