You are here: ABI » ThesesHome » RNAAligner

Area

Computational RNA analysis

Topic

Extending structural RNA alignment algorithm to find regulatory motifs in mRNAs

The project builds on work on structural alignment by Bauer, Klau and Reinert [1,2], who proposed an algorithm for structural RNA alignment based on mathematical optimization. The underlying model represents RNA structures as annotated sequences and aligns them using Lagrangian relaxation, optimizing a combination of sequence and structure score. As shown in [1], the corresponding software tool lara belongs to the top structural alignment methods in the field. Nevertheless it is still more or less ignored by the community, which is due to limited (i) functionality, (ii) availability, and (iii) applicability.

The aim of this project is to overcome these restrictions by

  • Transferring and extending the implementation in SeqAn,a widely used C++ library for sequence analysis
  • Focusing on and extending the strengths of the algorithm, which include the ability to compute pseudoknot alignments and to align rather long RNA sequences
  • Letting the algorithmic work guide by a concrete case study. At the Netherlands Cancer Institute (Molecular Carcinogenesis group) a unique set of functionally related human mRNAs have recently been identified in a functional screen. Some of these mRNAs contain positively validated regulatory motifs in their 5' UTR. See [3] for an examples of important structural motifs in messenger RNA. The aim is to study the whole set for novel regulatory structural motifs that are likely to be evolutionary conserved. Therefore, it may be necessary to develop a local or semi-global version of the algorithm. It may also be helpful to look at results from related alignment algorithms and get acquainted with other tools in computational RNA analysis.

The implementation will be realized and tested in C++ within the SeqAn library for computational sequence analysis. As this is a cooperation project with the Life Sciences group of the Netherlands Centre for Mathematics and Computer Science (CWI), parts of the project will be carried out in Amsterdam (approx. 2-4 weeks, costs are covered).

Timeline

  • [Week 1-4] Porting the lara C++ code to SeqAn, getting familiar with computational RNA analysis
  • [Week 4-12] Starting with the case study. Identifying further directions that need to be improved in order to answer the biological question.
  • [Week 4-12] In parallel. Realizing first extensions such as, e.g., semi-global alignment.
  • [Week 12-20] Focusing on the key topic that has been identified in phase I of the project, which can be, e.g., RNA motif search, local alignments, computing very long alignments or dealing with pseudoknots. Implementing, extensive testing and benchmarking.
  • [Week 20-24] Finishing experiments, writing up.

The stay at CWI should take place between week 4 and week 16

[1] Markus Bauer, Gunnar W. Klau and Knut Reinert. Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization. BMC Bioinformatics, Vol. 8, No. 271, BioMed Central, 2007.

[2] Markus Bauer. A combinatorial approach to RNA sequence-structure alignments. PhD thesis, FU Berlin, 2008. http://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000004656

[3]: Interesting background for motifs in mRNA: http://www.nature.com/nature/journal/v475/n7354/full/nature10126.html
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback