advertisement

RNA sequence structure alignement

50 %
50 %
advertisement
Information about RNA sequence structure alignement
Entertainment

Published on November 28, 2007

Author: Ethan

Source: authorstream.com

advertisement

Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment:  Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment by Christian Ehrlich Song1, C. Liu1, X. Huang2, R.L. Malmberg3, Y. Xu4, and L.Cai1 1 Dept. of Computer Science, Univ. of Georgia, USA 2 Dept. of Computer Science, Arkansas State Univ., USA 3 Dept. of Plant Bio., Univ. of Georgia, USA 4 Dept. of Biochemistry and Molecular Bio., Univ. of Georgia, USA WABI2005, LNBI3692, pp. 376-388, 2005. Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Structure-sequence alignment http://legionella.cu-genome.org http://www.sanger.ac.uk Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Motivation non-coding (nc)RNA - gene regulation - chromosome replication - RNA modification Why not simply search for the consensus sequence? structure search is way more accurate !!! Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Existing methods for structure-sequence alignment Integer Linear Programming (ILP) (Lenhof, Reinert, Vingron; 1998) huge number of linear constrains Divide-and-conquer based on ‘open links’ (Xu, Xu, Uberbacher; 1998) only useable for very small RNAs Standard DP extended to handle pseudoknots (Umura et al.; 1999) memory overhead, computational intractable Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Main concept (Song et al.; 2005) 1 2 3 4 5 6 RNA structure 1 2 3 4 5 6 C N Structure graph a b c d e f Genomic sequence N C a b c d e f Sequence graph Tree-decomposition Dynamic programming Struc-Seq aligned! Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Constructing the structure graph H 1 2 3 4 5 6 RNA consensus structure Obtain RNA consensus structure from multiple alignment or DB (e.g. Rfam) Identify base-pairing regions Each base-pairing region is modeled as vertex. Each structural interaction is modeled as undirected edge. Each loop is modeled as directed edge. N- and C-terminus are modeled as source and sink, respectively.. done! Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Constructing the sequence graph G Genomic sequence Identify candidate region in the sequence (take the k best) For each set of candidates construct a structure graph Connect all pairing candidate regions Add N- and C-terminus done! Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Tree-decomposition 1 2 3 4 5 6 C N Structure graph H 1 2 3 1 2 6 1 6 5 N 1 C 4 5 6 3 4 5 2 3 4 Tree-decomposition T ‘all‘ tree properties are conserved! u v Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Dynamic programming approach (bottom up) 1 2 6 1 6 5 4 5 6 Tree-decomposition g h f A mapping is valid if for any set of overlapping candidates, at most one can be selected in the subgraph and 1. 2. d1 d2 d3 Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Objective function S1 - the alignment between a structural unit u and its candidate S2 - the alignment between the interaction of two structural units (u,v) and the interaction of the coresponding candidates f(u),f(v) S3 - the alignment between a loop and the coresponding candidate loop Dynamic programming Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Sensitivity/Selectivity Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Performance Take this massage home!:  Take this massage home! Main concept 1 2 3 4 5 6 RNA structure 1 2 3 4 5 6 C N Structure graph a b c d e f Genomic sequence N C a b c d e f Sequence graph Tree-decomposition Dynamic programming Struc-Seq aligned! Take this massage home!:  Take this massage home! Why use struc.-seq. alignment based on tree-decomposition? Sensitivity and selectivity comparable to other struc-seq alignment models (e.g. CMs) Speed-up of about 30 to 40 times over other methods Applicable in large sequences (e.g. virus/bacteria genome) Handling of pseudoknot-structures is very easy Introduction Graph generation Alignment Results:  Introduction Graph generation Alignment Results Referenzes Yinglei Song et al.: Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment. WABI2005, LNBI3692, pp. 376-388, 2005. Yinglei Song et al.: Tree Decomposition Based Fast Search of RNA Structures Including Pseudoknots in Genomes. unpublished Yinglei Song et al.: A Tree-Decomposition Approach to Protein Structure Prediction. unpublished H.L. Bodlaende: A Tourist Guide through Treewidth. Acta Cybernetica, 11:1–21, 1193. A. Ehrenfeucht et al.: An O(n2) Divide-and-Concer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs. Journal of Algorithms 16, 283-294 (1994) Any questions?:  Any questions?

Add a comment

Related presentations

Related pages

MARNA - Structure Alignment - Freiburg RNA Tools

MARNA computes multiple sequence-structure alignments considering a single fixed structure for each sequence only.
Read more

Sequence alignment - Wikipedia, the free encyclopedia

In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a ...
Read more

Structural alignment - Wikipedia, the free encyclopedia

Structural alignment attempts to establish homology between two or more polymer structures based on their shape and three-dimensional conformation.
Read more

ALIGNMENTS - ONLINE ANALYSIS TOOLS

COMPARE TWO SEQUENCES: ALIGN Query using sequence data ... a web server for the pairwise global or local alignment of RNA secondary structures.
Read more

ExPASy: SIB Bioinformatics Resource Portal - Categories

DNA; RNA; Protein; Cell; Organism ... SBC • Fast and accurate multiple sequence alignment • LALIGN ... T-Coffee • sequence and structure multiple ...
Read more

4SALE – A tool for synchronous RNA sequence and ...

4SALE fills this gap. The application allows a fast sequence and synchronous secondary structure alignment for large data sets and for the first ...
Read more

Freiburg RNA Tools

Freiburg RNA tools provides online access to a series of RNA research tools developed by the Freiburg Bioinformatics Group for sequence-structure ...
Read more

RNA Structure and Sequence alignment - FOLDALIGN

RNA Structure and Sequence alignment NEW: Foldalign version 2.5 is the newest version and webserver. Get the software here. Foldalign version 2.1.1 is ...
Read more

BBCU - Protein structure - Sequence alignment

Toolbox > Protein Structure > Analysis > Sequence Alignment Structure ... and sequences of proteins and/or DNA ... sequence-to-structure alignment.
Read more

3D-Structure-Motifs Aware Sequence Structure Alignment of RNAs

of sequence structure alignment is given in table 2.3, ... Strasbourg. This alignment included 799 RNA sequences from the ribosomal 16S family.
Read more