Non-Coding RNAs: computational challenges and applications
28-30 April 2008
Antalya, Turkey

Organisers:

Cenk Sahinalp, Lab for Computational Biology, Simon Fraser University, BC, Canada & Sabanci University, Istanbul, Turkey
Ugur Sezerman, Biological Sciences and Bioeng. Prog., Sabanci University , Istanbul Turkey
Ron Shamir, Computer Science Department, Tel Aviv University, Israel
Rolf Backofen, Institute of Computer Science, University of Freiburg, Germany

Draft Report

Summary

Experts in RNA algorithms and applications met in the ESF funded workshop on ncRNAs: computational challenges and applications in Antalya , Turkey in late April 2008. Hot topics discussed in the workshop included ncRNA detection and profiling via novel sequencing technologies and ncRNA mapping, ncRNA gene discovery, RNA structure prediction, RNA-RNA interaction prediction and regulatory RNA target detection, ncRNA function determination, especially the role of ncRNAs in development and disease. There were a number of distinguished speakers who presented their cutting edge research in ncRNA bioinformatics and its current and potential applications.

There was a section on redefining the genotype by integrative studies: computational and statistical tools.The unifying point of this section is the redefinition of the concept of 'genotype', which has remained for a long time within the classical genetic definition even after the advent of molecular genetics. Recent developments in the technology of the measure of gene-expression levels and fine-scale detection of genome alterations have made it possible to conceive phenotypic traits in terms of variations in the levels of gene expression, which can be due to SNPs in genes and/or promoters; changes in DNA copy numbers; interaction with other RNAs; epigenetic factors; interaction with regulatory proteins.

There were also series of talks focusing on identification of microRNAs from deep sequencing experiments. These talks focused on difficulties of such tasks and the benefits arising from the outcome of such experiments.

Scientific Content

The first speaker was Ron Shamir (Tel Aviv University) who talked about analyzing regulatory RNAs using sequence and interaction networks. Shamir talked about Amadeus, a novel de-novo RNA motif detection tool for genome wide detection of regulatory RNA (especially miRNA) targets. Shamir also talked about a microarray based methodology for miRNA profiling in a variety of stem cell lines and the identification of cell-type-specific differences which may have a role in the regulation of self-reneval and pluripotence.

The first talk by Ivo Hofacker (University of Vienna) was on the detection of ncRNAs genes – which do not have easily detectable sequence signals such as open reading frames and codon usage. Yet many ncRNAs can by detected by comparative methods, such as RNAz, based on on the stability and conservation of RNA secondary structures. RNAz is very suitable for use by computational screens even on large mammalian genomes, and provide evidence for tens of thousands functional RNAs in mammalian genomes. Interestingly, most of these ncRNA candidates cannot be assigned to any of the known ncRNA families.

Rolf Backofen (University of Freiburg) talked about new comparative methods for RNA motif detection, a difficult problem due to low sequence conservation of RNA. However, due to high structure conservation, simultaneous consideration of sequence and structure may prove to work well. This general approach is used by LocaRNA alignment package which is inspired by Sankoff's RNA structure/sequence alignment algorithm but is much faster by the use of a few heuristic shortcuts. LocaRNA is an integral part of the MEMERIS program for motif detection, which considers secondary structure properties as well as sequence conservation, which has been used to investigate regulation of alternative splicing.

Cenk Sahinalp talked about RNA-RNA interaction prediction and ncRNA target search. The inteRNA tool that was developed at the Lab for Computatioal Biology at SFU models the RNA-RNA interaction prediction as a total free energy minimization problem and estimates the binding energies of kissing loop pairs as per earlier studies of pseudoknots energy predictions. InteRNA predicts all known non-trivial interacting RNA binding sites accurately in reasonable amount of time by folding the two interaction partners together via dynamic programming. I also introduced our ncRNA target search program pRuNA, which makes extensive use of inteRNA and our ncRNA gene prediction tool smyRNA .

A second talk by Ivo Hofacker was on predicting ncRNA targets. Hofacker's approach aims to (i) speed up earlier algorithms such as inteRNA which can be sometimes slow for long RNA sequences and (ii) introduce additional constraints such as target accessibility, which is not considered in detail by inteRNA and others.

3'-UTR regions contain binding sites for several regulatory elements which play an important role in thepost-transcriptional control of gene expression, regulating mRNA stability, localization and translation efficiency. Michele Caselle of University of Torino discussed a computational methodology aimed at the identification of putative regulatory elements in human 3'-UTR regions, with a focus for miRNA binding sites.

We also had a number of young researchers who were invited to present their cutting edge algorithmic work on RNA structure prediction. This is a problem that has stood unresolved despite a 40 year effort. It's been argued that much of the problem is due to limited availability of thermodynamic parameters (especially those for loop structures) which form the basis of the most popular RNA structure prediction tools such as mfold. Chuong (Tom) Do (Batzoglou Lab, Stanford University ) aims to take care of this problem by computationally learning those parameters through recently complied sets of RNA secondary structures. Do's tools are based on discriminative machine learning techniques, namely, log-likelihood and margin-based models, which provide parameters that improve the accuracy of conventional RNA folders significantly. Emidio Capriotti (CIPF) talked about their tool SARA that is used for RNA structure alignment. Yousuf Malek talked about Machine learning base web server for microRNA prediction. Stephen Jannsen from Bielefeld University talked about shape based indexing of RNA families to enable faster search. Ludovica Montanucci ( Bologna University ) discussed possible relationships between SiRNA and MiRNA targets. Frederic Reiner from CRS4 tallked about miR*Ware which is a novel target mRNAs data integration approach for tissue-oriented microRNAs. Alexander Churkin talked on RNAmute which aims to computationally predict the minimal number of mutations required to disrupt important secondary structure motifs in RNA viruses.

There were several talks from Dirk Walther's Lab at Max Planck Institute for Molecular Plant Physiology. First one was given by Liam Childs on capturing RNA functionality in graph properties. Patrick May discussed riboswitch metabolite interactions. There were two talks from Sabanci University, Tugrul Tekbulut talked about finding MirNA targets using constraint programming and Hilal Kosucu talked on RNA secondary structure prediction using a simulated annealing algorithm.

Later, Rahele Salari (Lab for Computational Biology, SFU) suggested an alternative energy model to the nearest neighbors thermodynamic model which considers additional features such as the energy density of a substructure towards predicting global secondary structure. The goal of this Densityfold approach is to emphasize locally stable structures, which can act as kinetic traps, by providing them an additive, length normalized contribution to the overall optimization function. Densityfold accurately predicts the secondary structure of a large number of ncRNA families which are inaccessible with conventional thermodynamic means. When combined with programs such as CONTRAfold and mfold, Densityfold provides a powerful tool for structure prediction: a computational oracle which picks the right tool for the right RNA sequence based on the nearest neighbors classification method was also introduced and is shown to significantly outperform all known tools for RNA secondary structure prediction.

Zohar Yakhini (Department of Computer Science, Tel Aviv University and Agilent Laboratories, Israel – United States) gave a wide and structured talk on novel analytical approaches for the integration of different measures of transcriptomic and genomic data, from miRNA expression levels to DNA copy number, and on the consequent novel view on the definition of a ‘molecular genotype' based on the integration of different data sources.

Zohar illustrated first how alterations at the genome structure level influence the gene expression level. Alterations in genomic content and changes in gene expression levels are central characteristics of tumors and seem to be pivotal to the tumorigenic process. A recent work which combined array CGH results with gene expression profiling performed on the same tumor samples was illustrated. A set of genes with concordant changes in DNA copy number and expression levels was identified, i.e. overexpressed genes located in amplified regions and underexpressed genes located in deleted regions. The joint analysis of array CGH and gene expression analysis thus highlighted genes with concordant changes in expression and copy number that may be critical to cancer development and progression.

Another significant example of integration between complementary approaches to genome analysis refers to melanoma and MITF. By integrating SNP array-based genetic maps with gene expression signatures derived from NCI60 cell lines, Zohar illustrated the identification of the melanocyte master regulator MITF (microphthalmia-associated transcription factor) as the target of a novel melanoma amplification. It was found that MITF amplification was more prevalent in metastatic disease and correlated with decreased overall patient survival. Hence, MITF could represent a distinct class of 'lineage survival' or 'lineage addiction' oncogenes required for both tissue-specific cancer development and tumour progression.

Two computational tools, publicly available, were then presented: Gorilla - A Tool For Discovery And Visualization of Enriched GO Terms in Ranked Gene Lists, and DRIM, a tool for discovering significantly overrepresented motifs in a list of ranked DNA sequences. This computational tool was applied in a work which described the fine-scale architecture of CNV regions in the human genome. This study used an high-resolution array-based comparative genomic hybridization (aCGH) platform that targeted known CNV regions of the human genome at approximately 1 kb resolution. The genomic DNAs of 30 individuals from four HapMap populations was sampled and the results revealed that 1020 of 1153 CNV loci (88%) were actually smaller in size than what is recorded in the Database of Genomic Variants based on previously published studies. Interesting sequence features were retrieved in the CNV boundaries, highlighting the role of homologous recombination in CNVs. The study concludes that the total genomic content of currently known common human CNVs is likely smaller than previously thought.

The last aspect of the investigation of transcriptional landscape illustrated by Zohar was the role of microRNAs in two specific projects: the development of an ‘Universal Onco-miRs chip' and a discovery study on the role of miRNAs in IPF. IPF is an inflammatory lung disease affecting around 100.000 people in the US alone; miRNA profiling on 10 samples as opposed to 10 controls was performed and a constant overexpression of mir145 (and downregulation of the associated predicted target genes) was consistently observed. Statistical methods applied to both projects were then illustrated.

Finding the needles in the haystack: identification of microRNAs from deep sequencing experiments.

The advent of (relatively) inexpensive deep sequencing techniques is impacting significantly on the new field of the identification and quantification of known, conserved and novel microRNAs from the results of deep sequencing experiments of small RNA libraries. This is not a trivial task, since many evidences now support the existence of a wide range of small mature ncRNA transcripts, derived from the quasi-random cleavage of small RNAs such as tRNAs or snoRNAs, lying exactly in the range of interest of the ‘miRNA hunters' (from 20 to 30 nts). In addition, only molecules derived from genome precursors which can fold in the proper shape can be considered as reliable candidates for laboratory validation. Three different computational pipelines for the analysis of high-throughput small RNA libraries were presented: Zeynep Arziman from Germany illustrated Mirseq, an R package applied to the primary processing and analysis of single and multiplexed small RNA libraries with a special focus on microRNA prediction in D.melanogaster. Alessandro Guffanti from Italy talked about an analysis procedure based on genomic and biological assumptions applied to human and mouse sequences. Eugene Berezikov from Hubrecht talked about his extensive discovery experience on miRNA identification from deep sequencing data, adding a fascinating ‘biological' view to this complex topic.

The importance of sequence conservation is very well illustrated by the progressive identification and cloning of miRNAs, from worm-specific to conserved. If one looks at the genome aspect, the conservation pattern of the pre-miRNA stands clearly against the background due to the genetic drift. This conservation pattern is also helpful in retrieving novel miRNA sequences which are nearby already identified one. It is then possible to search for novel miRNAs starting from conserved regions between human and mouse or human and rat and then filter for regions which fold back correctly. The crossing of the various conserved miRNAs revealed many hundred of novel candidates by the so called ‘Phylogenetic shadowing'. This approach brought to the prevision of many hundred possible novel miRNA sequences.

A first experiment in deep sequencing between human and chimp brain revealed a total of 893 reads representing novel miRNAs on more than 180.000 for each of human and chimpanzee, thus it is evident that although the number of predicted novel miRNAs in eukaryotic genome is some hundreds, it will be more and more difficult to find novel sequences. This also adds to the consideration that many of the novel reads will be tissue-specific, and this is reflected by the scarce conservation between phyla in novel sequences. Novel conserved miRNAs will be nearly always expressed at a low level.

An improved computational pipeline was applied to deep sequencing results from human and macaque brain regions, where again the percentage of known miRNAs was around 80% in each experiment and it was definitively confirmed that there is a different dynamic of expression between known (universal) and novel (tissue-specific) miRNA sequences.

Some general observations were very interesting: many low abundant miRNA candidates may be extremely restricted in their expression, even cell-specific. Some mirBase miRNAs - and even many low abundance novel miRNAs - clearly derive from repeats and are transcribed by PolIII, but still are considered to be interesting for a primary evaluation. Also miRNA sequences derived from repeats were illustrated, and mi-RNA like snoRNAs representing RNA loci which are few nucleotides away from becoming miRNA-like hairpins. Berezikov then illustrated the discovery of mirtrons in mammals. Mirtrons are intronic miRNA precursors which pass through an alternative biogenesis pathway.

There are thus three main venues to miRNA evolution: duplication of existing miRNAs; RNAs derived from repeats, non-coding RNAs; miRNAs derived from introns.

Finally a number of examples underlining the real utility of deep sequencing for quantification of miRNA sequences was illustrated with a number of interesting examples on transcripts expressed in cerebellum.

Genome alterations and small RNA expression

Some interesting talks focused on the interrelations between genome alterations, miRNA expression levels.

Mark Donoghue, Patrick May and Ozlen Konu presented a bioinformatic analysis and microarray expression profiling of miR-21 sensitive transcriptome of MCF7 cells. The endogenous mir-21 was knocked down by anti-miR-21 in MCF7 cells. Total RNA from amti-miR-21 and appropriate controls was used for profiling differentially expressed transcripts (miR-21 sensitive transcriptome). A total of 140 transcripts were identified as differentially expressed only in anti-21 treated samples compared to untreated samples. Functional interpretation of the results showed that 25% of the genes were involved in regulation, 9.62% were involved in apoptosis and regulation of programmed cell death and the rest was involved in other biological processes. Several approaches are being used to identify overrepresentation of miR-21 target sites in the differentially expressed trascripts compared to full genome. A pattern which is apparent is that part of the target genes are downregulated also at the level of gene expression. Begum Akman presented potential roles of non-coding RNAs in regulation of an oncogene candidate in MCF7 cells.

Serkan Tuna illustrated a detailed search of bioinformatics resources and databases to identify common genomic instability regions in breast cancer. The group investigated more than 30 miRNA genes located to the common genomic instability regions in breast cancers and found that 47% of the 36 microRNA genes identified in the region showed significant fold number changes compared to an internal control gene, GAPDH, in 3 or more of the total number of 22 breast cancer cell lines in terms of genomic gain or loss by semi-quantitative PCRs. These results may point out that these microRNAs can function as oncogenes or tumor suppressors. Candidate microRNAs on some chromosomal bands, that are commonly amplified/lost in breast cancer cells, are being investigated in terms of their expression levels by RT-PCR in normal breast tissue and breast cancer cell lines.

A very interesting description of the strong links between genome alterations, ncRNAs, disease phenotypes was given by Asli Silahtaroglu of the Wilhelm Johannsen Centre for Functional Genome Research. She presented the Mendelian Cytogenetics Network Online Database and a number of very interesting evidences related to the identification of ncRNA and transcribed non-genic conserved elements in chromosome regions involved in disease-related deletions and chromosomal rearrangements. When the breakpoint of a translocation is not within a gene, for instance, looking at the nearby ncRNA structure and expression gave interesting results.

•  Asli also illustrated a very exciting tool for miRNA expression validation in frozen tissue sections. shown that a simple systemic delivery of locked-nucleic-acid-modified oligonucleotide (LNA-antimiR) effectively antagonizes the liver-expressed miR-122 in non-human primates, without any evidence for LNA-associated toxicities or histopathological changes. The treatment was accompanied by depletion of mature miR-122 and dose-dependent lowering of plasma cholesterol.

They extensively searched bioinformatics resources and databases to identify common genomic instability regions in breast cancer. We investigated more than 30 miRNA genes located to the common genomic instability regions in breast cancers. We have found that 47% of the 36 microRNA genes show significant fold number changes compared to an internal control gene, GAPDH, in 3 or more of the total number of 22 breast cancer cell lines in terms of genomic gain or loss by semi-quantitative PCRs. These results may point out that these microRNAs can function as oncogenes or tumor suppressors. Candidate microRNAs on some chromosomal bands, that are commonly amplified/lost in breast cancer cells, are beibg investigated in terms of their expression levels by RT-PCR in normal breast tissue and breast cancer cell lines.Bioinformatical studies are also being carried out on a number of candidate microRNAs.

Aymeric Fouquier d'Herouel of KTH talked on identification of non-coding RNA in Enterococcus faecalis.In this work they developed a method for genome wide ncRNA and target search in the genome of Enterococcus faecalis which is eventually applicable to other prokaryotes and to some extent to eukaryotic and viral genomes.

Assessment of the results & impact of the event

The main objective of the meeting were to discuss new algorithms, software tools and their applications in non-coding RNA bioinformatics. In particular we aimed to bring in some of the world's leading scientists who have made significant recent progress in (i) computationally identifying the loci of non-coding RNAs on a genome sequence, (ii) intelligently using novel sequencing technologies towards identifying all functional non-coding RNA sequences in an organism, (iii) predicting the exact form of interactions among non-coding RNAs, between non-coding RNAs and coding RNAs, non-coding RNAs and DNA as well as proteins and small molecules, and, as a result, (iv) understanding the exact functionality of non-coding RNAs, (v) non-coding RNA databases (e.g. Rfam) and algorithms for efficient search in such databases. Central to all these goals are the (v) computational methods to improve the accuracy of the existing tools for predicting the independent structure of an RNA sequence with or without pseudoknots. Once the functionality and the structure of known RNAs are well understood, one can hope to develop (vi) novel non-coding RNAs for specific purposes, for example for regulating the expression of targeted genes. In principle, these artificial regulatory RNA molecules could be employed as drugs for the treatment of a variety of human diseases such as several types of cancer, rheumatoid arthritis, brain diseases and viral infections.

Overall the meeting inspired several intersting discussions carried out during question sessions, coffee breaks and lunch breaks.RNA'08 brought together 86 prominent scientists ( 44 from Turkey and 42 from Europe and America) from 12 different countries (Italy, Spain, Germany, Austria, U.S.A, England, Holland, Finland, Israel, Palestine, Canada, Greece and Sweden) and promoted to set up a forum for discussing some of the existing and future challenges related to non-coding RNA algorithms and their applications and emerging technologies and related computational tools that can help to address these challenges.

Programme

Monday 28 April 2008

Session 1

Session Chair: Cenk Sahinalp

09.00 – 09.10 Opening Remarks

09.10 – 10.00 Ron Shamir , Department of Computer Science, Tel Aviv University
Analysis of regulatory microRNAs using sequence and interaction networks, Abstract #1
10.00 – 10.20 Liam Childs , AG Bioinformatics, Max Planck Institute
Capturing RNA functionality in graph properties, Abstract #11
10.20 – 10.40 Michele Caselle , Dept. of theoretical Physics, University of Torino
Identification of microRNA targets and post-transcriptional regulatory networks, Abstract #12

10.40 – 11.00 Coffee Break

11.00 – 11.50 Ivo Hofacker, Institute for Theoretical Chemistry, University of Vienna
From noncoding RNA search to annotation, Abstract #2
11.50 – 12.10 Emidio Capriotti , Dept. of Bioinformatics, Centro de Investigación Príncipe Felipe (CIPF)
SARA: a tool for RNA Structure Alignment, Abstract #13
12.10 – 12.30 Yousef Malik , Bioinformatics and Molecular Biology, The Regional R&D Center - The Galilee Society
A web-server for microRNA prediction- Machine Learning Approach, Abstract #14

12.30 – 14.00 Lunch Break

Session 2

Session Chair: Ron Shamir

14.00 – 14.30 Poster Session 1

14.30 – 15.20 Cenk Sahinalp , Lab for Computational Biology, Simon Fraser Uni.; Sabanci University
RNA-RNA Interaction Prediction, Abstract #3
15.20 – 15.40 Stefan Janssen , Practical Computer Science, Bielefeld University
Shape based indexing for faster search of RNA family databases , Abstract #15
15.40 – 16.00 Alexander Churkin , Dept. of Computer Science, Ben-Gurion University
RNAMute: Algorithmic Advances and New Applications in RNA Viruses, Abstract #16

16.00 – 16.20 Coffee Break

16.20 – 17.10 Rolf Backofen , Computer Science Institute, University of Frieburg
Motif Detection under RNA Structural Constraints, Abstract #4
17.10 – 17.30 Tugrul Tekbulut , Biology and Bioengineering, Sabanci University
microRNA Target Prediction by Constraint Programming, Abstract #17
17.30 – 17.50 Zeynep Arziman Büyükboduk , Signaling and Functional Genomics, German Cancer Research Center (DKFZ)
Mirseq: An R package to analyze the high-throughput small RNA libraries, Abstract #18

17.50 – 18.00 Coffee Break

18.00 – 18.30 Poster Session 1

Tuesday 29 April 2008

Session 3

Session Chair: Rolf Backofen
09.10 – 10.00 Zohar Yakhini , Department of Computer Science, Tel Aviv University; Agilent Labs
Measuring miRNA expression and its role in human disease, Abstract #5
10.00 – 10.20 Alessandro Guffanti , Nanotechnologies Laboratory, Institute of Biomedical Technologies, CNR
A genome-oriented bioinformatic analysis pipeline for detecting putative microRNAs from 454 large-scale sequencing experiments, Abstract #19
10.20 – 10.40 Ludovica Montanucci , Biocomputing Group, University of Bologna
In Silico Evidence of the Relationship between MiRNAs and SiRNAs, Abstract #20

10.40 – 11.00 Coffee Break

11.00 – 11.50 Asli Silahtaroglu , Wilhelm Johannsen Centre for Functional Genome Research,
University of Copenhagen
Non-Coding RNAs in Human Disease and Development, Abstract #6
11.50 – 12.10 Patrick May , Bioinformatics, Max Planck Institute of Molecular Plant Physiology
Exploring RNA-Ligand docking: Riboswitch-Metabolite Interactions, Abstract #21
12.10 – 12.30 Ivo Hofacker, Institute for Theoretical Chemistry, University of Vienna
From noncoding RNA search to annotation, Abstract #2

12.30 – 14.00 Lunch Break

Session 4

Session Chair: Ivo Hofacker

14.00 – 14.30 Poster Session 2

14.30 – 15.20 Özlen Konu , Department of Molecular Biology and Genetics, Bilkent University
Meta-analysis of miRNA expression datasets in connection with miRNA sequence features, Abstract #7
15.20 – 15.40 Mark Donoghue , Dept. of Biochemistry, University College Cork
Bioinformatic analysis and microarray expression profiling of miR-21 sensitive transcriptome of MCF7 cells, Abstract #22
15.40 – 16.00 Begüm Akman , Biological Sciences Dept., Middle East Technical University
Potential Roles of Non-coding RNAs in Regulation of an Oncogene Candidate, Abstract #23

16.00 – 16.20 Coffee Break

16.20 – 17.10 Chuong Tom Do , Computer Science Department, Stanford University
Discriminative approaches for RNA folding parameter estimation, Abstract #8
17.10 – 17.30 Christian Schudoma , Genes and Small Molecules, Max Planck Institute of Molecular Plant Physiology
Exploring Motif-based RNA 3D Modeling, Abstract #24
17.30 – 17.50 Hilal Kosucu , Dept. of Computer Science, University of Toronto
RNA Secondary Structure Prediction Using Simulated Annealing, Abstract #25

17.50 – 18.00 Coffee Break

18.00 – 18.30 Poster Session 2

Wednesday 30 April 2008

Session 5

Session Chair: Ugur Sezerman

09.10 – 10.00 Eugene Berezikov , Netherlands Institute for Developmental Biology, Hubrecht Institute
MicroRNA discovery by high-throughput sequencing, Abstract #9
10.00 – 10.20 Serkan Tuna , Biological Sciences Dept., Middle East Technical University
microRNAs localized to common genomic instability regions in breast cancer, Abstract #26
10.20 – 10.40 Aymeric Fouquier d'Herouel , Computational Biological Physics, Royal Institute of Technology
Identification of non-coding RNA in Enterococcus faecalis, Abstract #27

10.40 – 11.00 Coffee Break

11.00 – 11.50 Raheleh Salari , Lab for Computational Biology, Simon Fraser University
Nearest Neighbor Classification & Delocalized Nearest Neighbor Parameters for Improved RNA Structure Prediction, Abstract #10
11.50 – 12.10 Frederic Reinier , Bioinformatics Laboratory, CRS4, Center for Research and Development
miR*Ware: an approach for tissue-oriented microRNAs -- target mRNAs data integration, Abstract #28
12.10 – 12.30 Aikaterini Gkirtzou , Institute of Computer Science (ICS), FORTH and University of Crete, Heraklion, Greece
Mature miRNA identification via the use of a Naive Bayes classifier, Abstract #29
12.30 – 12.40 Closing Remarks