DNA Regulatory Binding Motif Search.pptVIP

DNA Regulatory Binding Motif Search Lecture Outline Gene regulation Definition of regulatory motif search CONSENSUS (“Greedy” Algorithm) Gibbs Sampler Key steps in transcription Initiation Elongation Termination Initiation Transcription Initiation Complex Upstream Regulatory Elements Lecture Outline Gene regulation Definition of regulatory motif search CONSENSUS (“Greedy” Algorithm) Gibbs Sampler Motif Identification What constitutes a motif? In S.cerevisiae typically 6-10 conserved bases – The motif Spacers varying in length (1-11bp) Usually located in the middle Subproblem #1 Having a collection of known binding sites Can we develop a representation to search for new binding sites? Subproblem # 2 Given a set of sequences containing binding sites for a common factor Can we discover their location in each sequence? Computational Approach Identify a set of genes believed to be controlled by the same regulatory mechanism (co-regulated genes). Extract regulatory regions of the genes (usually upstream sequences) to form a sample of sequences. Find some way to identify conserved elements (ungapped pattern) in these sequences, resulting in a list of potential regulatory sites. Motif Finding Problem Given a sample of sequences and an unknown pattern (motif) that appears at different unknown positions in each sequence, can we find the unknown pattern? Input: a set of sequences, each one with an unknown pattern at an unknown position. Output: the pattern and a set of starting positions of the pattern in each sequence. Why Not Use Multiple Alignment The motif is short and may appear in different location in different sequences. Most other areas are random. The problem is made more complicated since not every sequence contains a motif, due to: The upstream region used may not be long enough to include a regulatory site in every sequence. Usually, potential co-regulated genes are used to construct the sample, which means that we don’t know for sure whether all th