Structured RNAs and synteny regions in the pig genome

Background

Annotating mammalian genomes for noncoding RNAs (ncRNAs) is nontrivial since far from all ncRNAs are known and the computational models are resource demanding. Currently, the human genome holds the best mammalian ncRNA annotation, a result of numerous efforts by several groups. However, a more direct strategy is desired for the increasing number of sequenced mammalian genomes of which some, such as the pig, are relevant as disease models and production animals.

Results

We present a comprehensive annotation of structured RNAs in the pig genome. Combining sequence and structure similarity search as well as class specific methods, we obtained a conservative set with a total of 3,391 structured RNA loci of which 1,011 and 2,314, respectively, hold strong sequence and structure similarity to structured RNAs in existing databases. The RNA loci cover 139 cis-regulatory element loci, 58 lncRNA loci, 11 conflicts of annotation, and 3,183 ncRNA genes. The ncRNA genes comprise 359 miRNAs, 8 ribozymes, 185 rRNAs, 638 snoRNAs, 1,030 snRNAs, 810 tRNAs and 153 ncRNA genes not belonging to the here fore mentioned classes. When running the pipeline on a local shuffled version of the genome, we obtained no matches at the highest confidence level. Additional analysis of RNA-seq data from a pooled library from 10 different pig tissues added another 165 miRNA loci, yielding an overall annotation of 3,556 structured RNA loci. This annotation represents our best effort at making an automated annotation. To further enhance the reliability, 571 of the 3,556 structured RNAs were manually curated by methods depending on the RNA class while 1,581 were declared as pseudogenes. We further created a multiple alignment of pig against 20 representative vertebrates, from which RNAz predicted 83,859 de novo RNA loci with conserved RNA structures. 528 of the RNAz predictions overlapped with the homology based annotation or novel miRNAs. We further present a substantial synteny analysis which includes 1,004 lineage specific de novo RNA loci and 4 ncRNA loci in the known annotation specific for Laurasiatheria (pig, cow, dolphin, horse, cat, dog, hedgehog).

Conclusions

We have obtained one of the most comprehensive annotations for structured ncRNAs of a mammalian genome, which is likely to play central roles in both health modelling and production. The core annotation is available in Ensembl 70 and the complete annotation is available at http://rth.dk/resources/rnannotator/susscr102/version1.02.

Electronic supplementary material

The online version of this article (doi:10.1186/1471-2164-15-459) contains supplementary material, which is available to authorized users.     

An extended multi-objective mixed integer programming for water resources management through possibility theory

In this study, we develop an extended multi-objective mixed integer programming (EMOMIP) approach for water resources management under uncertainty, in which the parameters are fuzzy random variables while the decision variables are interval variables. Furthermore, some alternatives are considered to retrieve the difference between the quantities of promised water-allocation targets and the actual allocated water. Then, the proposed EMOMIP for the problem is solved by a new method using fuzzy random chance-constrained programming based on the idea of possibility theory. This method can satisfy both optimistic and pessimistic decision makers simultaneously. Finally, a real example is given to explain the proposed method.     

Simultaneous confidence intervals for pairwise multiple comparisons in a two-way unbalanced design

Turkey's (1953, The Problem of Multiple Comparisons, unpublished report, Princeton University) procedure is widely used for pairwise multiple comparisons in one-way ANOVA. It provides exact simultaneous pairwise confidence intervals (SPCI) for balanced designs and conservative SPCI for unbalanced designs. In this paper, we will extend Turkey's procedure to two-way unbalanced designs. Both the exact and the conservative methods will be introduced. The application of the new procedure is illustrated with sample data from two experiments.     

Simulating haplotype blocks in the human genome

SUMMARY: A bioinformatic tool was written to simulate haplotypes and SNPs under a modified coalescent with recombination. The most important feature of this program is that it allows for the specification of non-homogeneous recombination rates, which results in the formation of the so-called 'haplotype blocks' of the human genome. The program also implements different mutation models and flexible demographic histories. The samples generated can be very useful to better understand the architecture of the human genome and to investigate its impact in association studies searching for disease genes. AVAILABILITY: The SNPsim package is available at http://www.evolgenics.com/software     

A tree reconstruction method that is economical in the number of pairwise comparisons used

A fast method for reconstructing phylogenies from distance data is presented. The method is economical in the number of pairwise comparisons needed. It can be combined with a new phylogenetic alignment procedure to yield an algorithm that gives a complete history of a set of homologous sequences. The method is applicable to very large distance matrices. An auxiliary program was developed that simplifies large phylogenies without ignoring biologically essential features. A set of 213 globins from vertebrates, plants, and Vitreoscilla (a prokaryote) were analyzed using this method.      

Cinteny: flexible analysis and visualization of synteny and genome rearrangements in multiple organisms

Background  

Identifying syntenic regions, i.e., blocks of genes or other markers with evolutionary conserved order, and quantifying evolutionary relatedness between genomes in terms of chromosomal rearrangements is one of the central goals in comparative genomics. However, the analysis of synteny and the resulting assessment of genome rearrangements are sensitive to the choice of a number of arbitrary parameters that affect the detection of synteny blocks. In particular, the choice of a set of markers and the effect of different aggregation strategies, which enable coarse graining of synteny blocks and exclusion of micro-rearrangements, need to be assessed. Therefore, existing tools and resources that facilitate identification, visualization and analysis of synteny need to be further improved to provide a flexible platform for such analysis, especially in the context of multiple genomes.     

Gene-interleaving patterns of synteny in the Saccharomyces cerevisiae genome: are they proof of an ancient genome duplication event?

Background  

Recent comparative genomic studies claim local syntenic gene-interleaving relationships in Ashbya gossypii and Kluyveromyces waltii are compelling evidence for an ancient whole-genome duplication event in Saccharomyces cerevisiae. We here test, using Hannenhalli-Pevzner rearrangement algorithms that address the multiple genome rearrangement problem, whether syntenic patterns are proof of paleopolyploidization.     

Distribution of parental genome blocks in recombinant inbred lines

We consider recombinant inbred lines obtained by crossing two given homozygous parents and then applying multiple generations of self-crossings or full-sib matings. The chromosomal content of any such line forms a mosaic of blocks, each alternatively inherited identically by descent from one of the parents. Quantifying the statistical properties of such mosaic genomes has remained an open challenge for many years. Here, we solve this problem by taking a continuous chromosome picture and assuming crossovers to be noninterfering. Using a continuous-time random walk framework and Markov chain theory, we determine the statistical properties of these identical-by-descent blocks. We find that successive block lengths are only very slightly correlated. Furthermore, the blocks on the ends of chromosomes are larger on average than the others, a feature understandable from the nonexponential distribution of block lengths.     

Haplotype blocks and linkage disequilibrium in the human genome

There is great interest in the patterns and extent of linkage disequilibrium (LD) in humans and other species. Characterizing LD is of central importance for gene-mapping studies and can provide insights into the biology of recombination and human demographic history. Here, we review recent developments in this field, including the recently proposed 'haplotype-block' model of LD. We describe some of the recent data in detail and compare the observed patterns to those seen in simulations.     

An integer linear programming approach for finding deregulated subgraphs in regulatory networks

Deregulation of cell signaling pathways plays a crucial role in the development of tumors. The identification of such pathways requires effective analysis tools that facilitate the interpretation of expression differences. Here, we present a novel and highly efficient method for identifying deregulated subnetworks in a regulatory network. Given a score for each node that measures the degree of deregulation of the corresponding gene or protein, the algorithm computes the heaviest connected subnetwork of a specified size reachable from a designated root node. This root node can be interpreted as a molecular key player responsible for the observed deregulation. To demonstrate the potential of our approach, we analyzed three gene expression data sets. In one scenario, we compared expression profiles of non-malignant primary mammary epithelial cells derived from BRCA1 mutation carriers and of epithelial cells without BRCA1 mutation. Our results suggest that oxidative stress plays an important role in epithelial cells of BRCA1 mutation carriers and that the activation of stress proteins may result in avoidance of apoptosis leading to an increased overall survival of cells with genetic alterations. In summary, our approach opens new avenues for the elucidation of pathogenic mechanisms and for the detection of molecular key players.     

The evolution of development in Streptomyces analysed by genome comparisons

There is considerable information about the genetic control of the processes by which mycelial Streptomyces bacteria form spore-bearing aerial hyphae. The recent acquisition of genome sequences for 16 species of actinobacteria, including two streptomycetes, makes it possible to try to reconstruct the evolution of Streptomyces differentiation by a comparative genomic approach, and to place the results in the context of current views on the evolution of bacteria. Most of the developmental genes evaluated are found only in actinobacteria that form sporulating aerial hyphae, with several being peculiar to streptomycetes. Only four (whiA, whiB, whiD, crgA) are generally present in nondifferentiating actinobacteria, and only two (whiA, whiG) are found in other bacteria, where they are widespread. Thus, the evolution of Streptomyces development has probably involved the stepwise acquisition of laterally transferred DNA, each successive acquisition giving rise either to regulatory changes that affect the conditions under which development is initiated, or to changes in cellular structure or morphology.     

RNA-mediated programming of developmental genome rearrangements in Paramecium tetraurelia

The germ line genome of ciliates is extensively rearranged during development of the somatic macronucleus. Numerous sequences are eliminated, while others are amplified to a high ploidy level. In the Paramecium aurelia group of species, transformation of the maternal macronucleus with transgenes at high copy numbers can induce the deletion of homologous genes in sexual progeny, when a new macronucleus develops from the wild-type germ line. We show that this trans-nuclear effect correlates with homology-dependent silencing of maternal genes before autogamy and with the accumulation of approximately 22- to 23-nucleotide (nt) RNA molecules. The same effects are induced by feeding cells before meiosis with bacteria containing double-stranded RNA, suggesting that small interfering RNA-like molecules can target deletions. Furthermore, experimentally induced macronuclear deletions are spontaneously reproduced in subsequent sexual generations, and reintroduction of the missing gene into the variant macronucleus restores developmental amplification in sexual progeny. We discuss the possible roles of the approximately 22- to 23-nt RNAs in the targeting of deletions and the implications for the RNA-mediated genome-scanning process that is thought to determine developmentally regulated rearrangements in ciliates.     

Two level parallelism and I/O reduction in genome comparisons

Genome comparison poses important computational challenges, especially in CPU-time, memory allocation and I/O operations. Although there already exist parallel approaches of multiple sequence comparisons algorithms, they face a significant limitation on the input sequence length. GECKO appeared as a computational and memory efficient method to overcome such limitation. However, its performance could be greatly increased by applying parallel strategies and I/O optimisations. We have applied two different strategies to accelerate GECKO while producing the same results. First, a two-level parallel approach parallelising each independent internal pairwise comparison in the first level, and the GECKO modules in the second level. A second approach consists on a complete rewrite of the original code to reduce I/O. Both strategies outperform the original code, which was already faster than equivalent software. Thus, much faster pairwise and multiple genome comparisons can be performed, what is really important with the ever-growing list of available genomes.     

A comparative synteny map of Burkholderia species links large-scale genome rearrangements to fine-scale nucleotide variation in prokaryotes

Genome rearrangement events, including inversions and translocations, are frequently observed across related microbial species, but the impact of such events on functional diversity is unclear. To clarify this relationship, we compared 4 members of the Gram-negative Burkholderia family (Burkholderia pseudomallei, Burkholderia mallei, Burkholderia thailandensis, and Burkholderia cenocepacia) and identified a core set of 2,590 orthologs present in all 4 species (metagenes). The metagenes were organized into 255 synteny blocks whose relative order has been altered by a predicted minimum of 242 genome rearrangement events. Functionally, metagenes within individual synteny blocks were often related. The molecular divergence of metagenes adjacent to synteny breakpoints (boundary metagenes) was significantly greater compared with metagenes within blocks, suggesting an association between breakpoint locations and local fine-scale nucleotide alterations. This phenomenon, referred to as boundary element associated divergence, was also observed in Pseudomonas and Shigella, suggesting that this is a common phenomenon in prokaryotes. We also observed preferential localization of species-specific genes and insertion sequence element to synteny breakpoints in Burkholderia. Our results suggest that in prokaryotes, genome rearrangements may influence functional diversity through the enhanced divergence of boundary genes and the creation of foci for acquiring and deleting species-specific genes.     

Empirical Bayes inference of pairwise F(ST) and its distribution in the genome

Populations often have very complex hierarchical structure. Therefore, it is crucial in genetic monitoring and conservation biology to have a reliable estimate of the pattern of population subdivision. F(ST)'s for pairs of sampled localities or subpopulations are crucial statistics for the exploratory analysis of population structures, such as cluster analysis and multidimensional scaling. However, the estimation of F(ST) is not precise enough to reliably estimate the population structure and the extent of heterogeneity. This article proposes an empirical Bayes procedure to estimate locus-specific pairwise F(ST)'s. The posterior mean of the pairwise F(ST) can be interpreted as a shrinkage estimator, which reduces the variance of conventional estimators largely at the expense of a small bias. The global F(ST) of a population generally varies among loci in the genome. Our maximum-likelihood estimates of global F(ST)'s can be used as sufficient statistics to estimate the distribution of F(ST) in the genome. We demonstrate the efficacy and robustness of our model by simulation and by an analysis of the microsatellite allele frequencies of the Pacific herring. The heterogeneity of the global F(ST) in the genome is discussed on the basis of the estimated distribution of the global F(ST) for the herring and examples of human single nucleotide polymorphisms (SNPs).     

Loading problems with tool management in flexible manufacturing systems: A few integer programming models

In automated production systems like flexible manufacturing systems (FMSs), an important issue is to find an adequate workload for each machine for each time period. Many integer linear programming (ILP) models have been proposed to solve the FMS loading problems, but not all of them take tools into account. Those that do not consider tooling are quite unrealistic, especially when setup times are important with respect to processing times. When tool loading has to be handled by the model, the load assignment may have to be changed completely. In this article we consider FMSs with a tool management of the following type: the system works in time periods whose durations are fixed or not; and tools are loaded on the machines at the beginning of each time period and stay there for the whole time period. Tool changes may occur only at the end of each time period when the system is stopped. We present some integer programming models for handling these situations with several types of objectives. Emphasis is laid on the ILP formulations. Computational complexities are discussed.