Advances in Genomic Sequence Analysis and Pattern Discovery

The following sections are included:

• Contents

• Preface

• About the Editors

In this chapter we describe practical uses of computational regulatory motif discovery with the NestedMICA suite, with a focus on higher eukaryotic genomes. The NestedMICA algorithm is contrasted with other popular motif inference approaches. Recent developments of the algorithm and additions to analysis tools included with the suite are also described.

The practical use of NestedMICA is demonstrated with a case study where 120 Drosophila melanogaster regulatory motifs are inferred and validated computationally and experimentally. This work was previously published (Down et al., 2007) and is summarized here to demonstrate key principles of genome-scale regulatory motif studies for the research community. The importance of the interplay between computational and experimental work in finding and understanding functional elements is discussed. It is demonstrated how computationally discovered motifs can be associated with several independent lines of supporting evidence for their function, such as tissue-specific gene expression and inter-species conservation pattern. Similarity comparisons between computationally discovered and experimentally verified motif sets are also shown.

A practical tutorial of the NestedMICA is included to introduce the suite to researchers new to such tools. NestedMICA is used to reproduce the binding site motif of the STAT1 transcription factor using ChIP-seq data from a previously published study. We describe several new additions to the suite: a tool for analyzing motif hit overrepresentation in a positive sequence set versus a negative sequence set, a tool for finding statistically significant sequence motif matches, and a series of utilities for retrieving and preprocessing sequence regions for motif inference experiments.

Statistics of motifs have been widely revisited in the last 15 years due to the increasing availability of genomic sequences. The identification of DNA motifs with biological functions is still a huge challenge of genome analysis. Many functional and essential motifs have the particularity to be very frequent all along the chromosome or to be concentrated in some particular regions or to be preferentially co-oriented with the replication direction. It is therefore neccessary to distinguish significant features (e.g. frequency or skew) from what one could expect just by chance. Many approaches aiming at predicting functional motifs are then based on statistical properties of pattern occurrences in random sequences. R'MES has been initially designed to address the following question: “which are the motifs of length ℓ occurring with an exceptional frequency in this DNA sequence?” Now, it can also detect which motifs have a significant skew in a given sequence and deal with amino acid sequences. Soon it will allow researchers to compare the motif exceptionalities in two different sequences. This chapter presents the R'MES software package from a user's point of view and gives many practical examples, including recent DNA motif identifications.

The following sections are included:

• Introduction

• Results and Discussion
  • DNA repeats — important elements at genomic mid-range scale
  • Genomic Mid-Range Inhomogeneity (MRI): Nucleotide compositional extremes and sequence nonrandomness
    • Genomic MRI toolkit
    • (G+C)-rich and (A+T)-rich MRI regions are associated with several unusual DNA structures
    • R-rich/Y-rich MRI regions are associated with H-DNA triplex
    • DNA and RNA properties of GT-rich/AC-rich MRI regions
    • Alternated R/Y MRI regions adopt Z-DNA conformation
  • Weak periodicities and loose patterns
    • Chromatin periodicities
    • Periodicities in protein-coding sequences
    • Transcription-associated mutational asymmetry in mammals
  • A complex mosaic of MRI patterns and their fundamental importance
    • Intricate arrangement of genomic MRI patterns
    • The purpose of MRI regions

• Conclusions

• Acknowledgment

• References

Motif finding aimed at the de novo discovery of putative over-represented transcription factor binding sites in nucleotide sequences has been, and still is, one of the most challenging and open problems in bioinformatics. This article aims to provide a survey of different approaches and methods, from the days when typical instances were sets of promoters from co-expressed genes obtained from microarray (the “chips”) expression data, to the latest advances in the field, that permit more reliable identification of transcription factor target sequences through genome-wide experiments like Chromatin Immunoprecipitation (the “ChIPs”).

Analysis of a large number of RNA molecules indicates that variations in their nucleotide sequences do not necessarily convey differences in their secondary structures. Numerous methods have been developed to find patterns in RNA molecules, including the detection of structural motifs in families of noncoding RNAs (ncRNAs). When almost identical sequences render similar structures, these methods work well. However, when given structures differ from each other, there may not exist a motif common to all of them. In such cases, it is desirable to find out if such motifs are indeed present and if not, to determine the extent to which they are shared by the structures under study. We present here a novel tool to be used in finding common patterns among RNAs. In particular, we describe the use of this tool to find RNA structural elements in the human genome. Many of the RNA structures found by our method overlap with human genomic regions that have been previously found through other genome-wide studies aimed to discover conserved structured RNAs. Our method thus provides a complementary tool to the currently used approaches for mining conserved structured RNAs in the human genome.

Reliable benchmarking is a prerequisite for unbiased comparison of alternative approaches to motif discovery in DNA. This chapter focuses on datasets and procedures for benchmarking of discovery methods for transcription factor binding sites in genomic DNA. The general concept of benchmarking is discussed briefly, including the importance of using separate training data, test data and benchmark data. The need to distinguish between different aspects of the motif discovery process during benchmarking is also discussed. The various score functions for binding site predictions are presented, including both sequence based scoring and position-weight matrix based scoring as well as the relationship between these. The problem of unannotated binding sites in real sequences as well as the high rate of false positive predictions normally associated with motif discovery is also discussed in this context. Relevant criteria for good benchmark sets and some frequently used datasets are presented, together with new and improved sets for benchmarking of both single motif and module based prediction methods. Approaches towards genome-wide benchmarking using ChIP-chip and in particular ChIP-seq data are evaluated, including the problem of identifying functionally significant weak binding sites and benchmarking of methods using additional genome data as prior information. This is extended into a discussion of benchmarking without access to high-quality reference datasets of known binding sites. Finally, benchmarking of prediction methods of particular relevance to genome-based motif discovery is briefly discussed, including promoter and transcription start site prediction and nucleosome positioning.

This chapter focuses on the enhancement of existing plant regulatory databases by adding DNA word encyclopedias. The authors present DNA word encyclopedias for small sets of co-regulated sequences (C-repeat binding factor genes in wheat) and for intergenic regions of an entire genome (Arabidopsis thaliana). It is also shown how the resulting DNA word encyclopedia for Arabidopsis is incorporated into an existing repository, the Arabidopsis Gene Regulatory Information Server (AGRIS). This provides a model for how DNA word encyclopedias can be incorporated into organism specific regulatory databases.

Mining the increasing amount of genomic data requires very efficient tools. The efficiency can be improved with better algorithms, but one could also take advantage of the hardware itself to reduce the application runtimes.

It has been a few years that issues with heat dissipation prevent the processors from having higher frequencies. One of the answers to maintain Moore's Law is parallel processing. Grid environments provide tools for effective implementation of coarse grain parallelization. Recently, another kind of hardware has attracted interest: the multicore processors.

Graphics Processing Units (GPUs) are a first step towards massively multicore processors. They allow everyone to have some teraflops of cheap computing power in a personal computer.

The CUDA library (released in 2007) and the new standard OpenCL (specified in 2008) make programming of such devices very convenient. OpenCL is likely to gain a wide industrial support and to become a standard of choice for parallel programming. In all cases, the best speedups are obtained when combining precise algorithmic studies with a knowledge of the computing architectures. This is especially true with the memory hierarchy: the algorithms have to find a good balance between using large (and slow) global memories and some fast (but small) local memories.

In this chapter, we will show how those manycore devices enable more efficient bioinformatics applications. We will first give some insights into architectures and parallelism. Then we will describe recent implementations specifically designed for manycore architectures, including algorithms on sequence alignment and RNA structure prediction. We will conclude with some thoughts about the dissemination of those algorithms and implementations: are they today available on the bookshelf for everyone?

The following sections are included:

• Introduction

• The Molecular Revolution

• The Neutral Theory

• Positive Selection: The MHC Case

• Codon-Based Methods

• The McDonald—Kreitman Test

• Single Nucleotide Polymorphisms

• Conclusions: The Importance of Purifying Selection

• References

The following sections are included:

• Index