High-throughput methods such as EST sequencing, microarrays and deep sequencing have identified large numbers of alternative splicing (AS) events, but studies have shown that only a subset of these may be functional. Here we report a sensitive bioinformatics approach that identifies exons with evidence of a strong RNA selection pressure ratio (RSPR)--i.e., evolutionary selection against mutations that change only the mRNA sequence while leaving the protein sequence unchanged--measured across an entire evolutionary family, which greatly amplifies its predictive power. Using the UCSC 28 vertebrate genome alignment, this approach correctly predicted half to three-quarters of AS exons that are known binding targets of the NOVA splicing regulatory factor, and predicted 345 strongly selected alternative splicing events in human, and 262 in mouse. These predictions were strongly validated by several experimental criteria of functional AS such as independent detection of the same AS event in other species, reading frame-preservation, and experimental evidence of tissue-specific regulation: 75% (15/20) of a sample of high-RSPR exons displayed tissue specific regulation in a panel of ten tissues, vs. only 20% (4/20) among a sample of low-RSPR exons. These data suggest that RSPR can identify exons with functionally important splicing regulation, and provides biologists with a dataset of over 600 such exons. We present several case studies, including both well-studied examples (GRIN1) and novel examples (EXOC7). These data also show that RSPR strongly outperforms other approaches such as standard sequence conservation (which fails to distinguish amino acid selection pressure from RNA selection pressure), or pairwise genome comparison (which lacks adequate statistical power for predicting individual exons).

The trans-genomic query (TGQ) problem--enabling the free query of biological information, even across genomes--is a central challenge facing bioinformatics. Solutions to this problem can alter the nature of the field, moving it beyond the jungle of data integration and expanding the number and scope of questions that can be answered. An alignment table is a binary relationship on locations (sequence segments). An important special case of alignment tables are hit tables ? tables of pairs of highly similar segments produced by alignment tools like BLAST. However, alignment tables also include general binary relationships, and can represent any useful connection between sequence locations. They can be curated, and provide a high-quality queryable backbone of connections between biological information. Alignment tables thus can be a natural foundation for TGQ, as they permit a central part of the TGQ problem to be reduced to purely technical problems involving tables of locations.Key challenges in implementing alignment tables include efficient representation and indexing of sequence locations. We define a location datatype that can be incorporated naturally into common off-the-shelf database systems. We also describe an implementation of alignment tables in BLASTGRES, an extension of the open-source POSTGRESQL database system that provides indexing and operators on locations required for querying alignment tables. This paper also reviews several successful large-scale applications of alignment tables for Trans-Genomic Query. Tables with millions of alignments have been used in queries about alternative splicing, an area of genomic analysis concerning the way in which a single gene can yield multiple transcripts. Comparative genomics is a large potential application area for TGQ and alignment tables.

MOTIVATION: The exponential growth of sequence databases poses a major challenge to bioinformatics tools for querying alignment and annotation databases. There is a pressing need for methods for finding overlapping sequence intervals that are highly scalable to database size, query interval size, result size and construction/updating of the interval database. RESULTS: We have developed a new interval database representation, the Nested Containment List (NCList), whose query time is O(n + log N), where N is the database size and n is the size of the result set. In all cases tested, this query algorithm is 5-500-fold faster than other indexing methods tested in this study, such as MySQL multi-column indexing, MySQL binning and R-Tree indexing. We provide performance comparisons both in simulated datasets and real-world genome alignment databases, across a wide range of database sizes and query interval widths. We also present an in-place NCList construction algorithm that yields database construction times that are approximately 100-fold faster than other methods available. The NCList data structure appears to provide a useful foundation for highly scalable interval database applications. AVAILABILITY: NCList data structure is part of Pygr, a bioinformatics graph database library, available at http://sourceforge.net/projects/pygr

UNLABELLED: We have developed a quick web-based application for designing conserved genomic PCR and RT-PCR primers from multigenome alignments targeting specific exons or introns. We used Pygr (The Python Graph Database Framework for Bioinformatics) to query intervals from multigenome alignments, which gives us less than a millisecond access to any intervals of any genome within multigenome alignments. PRIMER3 was used to extract optimal primers from a gene of interest. QPRIMER creates an electronic genomic PCR image from a set of conserved primers as well as summary pages for primer alignments and products. QPRIMER supports human, mouse, rat, chicken, dog, zebrafish and fruit fly. AVAILABILITY: http://www.bioinformatics.ucla.edu/QPRIMER/.

BACKGROUND: Construction and interpretation of phylogenetic trees has been a major research topic for understanding the evolution of genes. Increases in sequence data and complexity are creating a need for more powerful and insightful tree visualization tools. RESULTS: We have developed 3D Phylogeny Explorer (3DPE), a novel phylogeny tree viewer that maps trees onto three spatial axes (species on the X-axis; paralogs on Z; evolutionary distance on Y), enabling one to distinguish at a glance evolutionary features such as speciation; gene duplication and paralog evolution; lateral gene transfer; and violation of the "molecular clock" assumption. Users can input any tree on the online 3DPE, then rotate, scroll, rescale, and explore it interactively as "live" 3D views. All objects in 3DPE are clickable to display subtrees, connectivity path highlighting, sequence alignments, and gene summary views, and etc. To illustrate the value of this visualization approach for microbial genomes, we also generated 3D phylogeny analyses for all clusters from the public COG database. We constructed tree views using well-established methods and graph algorithms. We used Scientific Python to generate VRML2 3D views viewable in any web browser. CONCLUSION: 3DPE provides a novel phylogenetic tree projection method into 3D space and its web-based implementation with live 3D features for reconstruction of phylogenetic trees of COG database.

Over the past few years, the analysis of alternative splicing using bioinformatics has emerged as an important new field, and has significantly changed our view of genome function. One exciting front has been the analysis of microarray data to measure alternative splicing genome-wide. Pioneering studies of both human and mouse data have produced algorithms for discerning evidence of alternative splicing and clustering genes and samples by their alternative splicing patterns. Moreover, these data indicate the presence of alternative splice forms in up to 80 per cent of human genes. Comparative genomics studies in both mammals and insects have demonstrated that alternative splicing can in some cases be predicted directly from comparisons of genome sequences, based on heightened sequence conservation and exon length. Such studies have also provided new insights into the connection between alternative splicing and a variety of evolutionary processes such as Alu-based exonisation, exon creation and loss. A number of groups have used a combination of bioinformatics, comparative genomics and experimental validation to identify new motifs for splice regulatory factors, analyse the balance of factors that regulate alternative splicing, and propose a new mechanism for regulation based on the interaction of alternative splicing and nonsense-mediated decay. Bioinformatics studies of the functional impact of alternative splicing have revealed a wide range of regulatory mechanisms, from NAGNAG sites that add a single amino acid; to short peptide segments that can play surprisingly complex roles in switching protein conformation and function (as in the Piccolo C2A domain); to events that entirely remove a specific protein interaction domain or membrane anchoring domain. Common to many bioinformatics studies is a new emphasis on graph representations of alternative splicing structures, which have many advantages for analysis.

SUMMARY: Recently, the Ka/Ks ratio test, which assesses the protein-coding potentials of genomic regions based on their non-synonymous to synonymous divergence rates, has been proposed and successfully used in genome annotations of eukaryotes. We systematically performed the Ka/Ks ratio test on 925 transcript-confirmed alternatively spliced exons in the human genome, which we describe in this manuscript. We found that 22.3% of evolutionarily conserved alternatively spliced exons cannot pass the Ka/Ks ratio test, compared with 9.8% for constitutive exons. The false negative rate was the highest (85.7%) for exons with low frequencies of transcript inclusion. Analyses of alternatively spliced exons supported by full-length mRNA sequences yielded similar results, and nearly half of exons involved in ancestral alternative splicing events could not pass this test. Our analysis suggests a future direction to incorporate comparative genomics-based alternative splicing predictions with the Ka/Ks ratio test in higher eukaryotes with extensive RNA alternative splicing.

MOTIVATION: Partial order alignment (POA) has been proposed as a new approach to multiple sequence alignment (MSA), which can be combined with existing methods such as progressive alignment. This is important for addressing problems both in the original version of POA (such as order sensitivity) and in standard progressive alignment programs (such as information loss in complex alignments, especially surrounding gap regions). RESULTS: We have developed a new Partial Order-Partial Order alignment algorithm that optimally aligns a pair of MSAs and which therefore can be applied directly to progressive alignment methods such as CLUSTAL. Using this algorithm, we show the combined Progressive POA alignment method yields results comparable with the best available MSA programs (CLUSTALW, DIALIGN2, T-COFFEE) but is far faster. For example, depending on the level of sequence similarity, aligning 1000 sequences, each 500 amino acids long, took 15 min (at 90% average identity) to 44 min (at 30% identity) on a standard PC. For large alignments, Progressive POA was 10-30 times faster than the fastest of the three previous methods (CLUSTALW). These data suggest that POA-based methods can scale to much larger alignment problems than possible for previous methods. AVAILABILITY: The POA source code is available at http://www.bioinformatics.ucla.edu/poa

SUMMARY: POAVIZ creates a visualization of a multiple sequence alignment that makes clear the overall structure of how sequences match and diverge in the alignment. POAVIZ can construct visualizations from any multiple sequence alignment source (e.g. PIR and CLUSTAL formats), and is valuable for revealing complex branching structure (such as domains, large-scale insertions / deletions or recombinations), especially in partnership with the Partial Order Alignment (POA) multiple sequence alignment program. AVAILABILITY: The Partial Order multiple sequence Alignment Visualizer (POAVIZ) program is available at http://www.bioinformatics.ucla.edu/poa

MOTIVATION: Consensus sequence generation is important in many kinds of sequence analysis ranging from sequence assembly to profile-based iterative search methods. However, how can a consensus be constructed when its inherent assumption-that the aligned sequences form a single linear consensus-is not true? RESULTS: Partial Order Alignment (POA) enables construction and analysis of multiple sequence alignments as directed acyclic graphs containing complex branching structure. Here we present a dynamic programming algorithm (heaviest_bundle) for generating multiple consensus sequences from such complex alignments. The number and relationships of these consensus sequences reveals the degree of structural complexity of the source alignment. This is a powerful and general approach for analyzing and visualizing complex alignment structures, and can be applied to any alignment. We illustrate its value for analyzing expressed sequence alignments to detect alternative splicing, reconstruct full length mRNA isoform sequences from EST fragments, and separate paralog mixtures that can cause incorrect SNP predictions. AVAILABILITY: The heaviest_bundle source code is available at http://www.bioinformatics.ucla.edu/poa

MOTIVATION: Progressive Multiple Sequence Alignment (MSA) methods depend on reducing an MSA to a linear profile for each alignment step. However, this leads to loss of information needed for accurate alignment, and gap scoring artifacts. RESULTS: We present a graph representation of an MSA that can itself be aligned directly by pairwise dynamic programming, eliminating the need to reduce the MSA to a profile. This enables our algorithm (Partial Order Alignment (POA)) to guarantee that the optimal alignment of each new sequence versus each sequence in the MSA will be considered. Moreover, this algorithm introduces a new edit operator, homologous recombination, important for multidomain sequences. The algorithm has improved speed (linear time complexity) over existing MSA algorithms, enabling construction of massive and complex alignments (e.g. an alignment of 5000 sequences in 4 h on a Pentium II). We demonstrate the utility of this algorithm on a family of multidomain SH2 proteins, and on EST assemblies containing alternative splicing and polymorphism. AVAILABILITY: The partial order alignment program POA is available at http://www.bioinformatics.ucla.edu/poa.