RNA sequence structure alignement

Information about RNA sequence structure alignement

Published on November 28, 2007

Author: Ethan

Source: authorstream.com

Content

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?

Related presentations


Other presentations created by Ethan

EB3
02. 10. 2007
0 views

EB3

bayarbaatar nov5
03. 10. 2007
0 views

bayarbaatar nov5

op sys jit lean
28. 11. 2007
0 views

op sys jit lean

Everything about flowers v4
07. 12. 2007
0 views

Everything about flowers v4

CW Overview Amald iJuly2007
15. 11. 2007
0 views

CW Overview Amald iJuly2007

DXM CSAM 9 07
29. 12. 2007
0 views

DXM CSAM 9 07

LT GAPS Fresh Produce2
31. 12. 2007
0 views

LT GAPS Fresh Produce2

Osmotic Pressure and Colloids
02. 01. 2008
0 views

Osmotic Pressure and Colloids

SPCC Training
09. 11. 2007
0 views

SPCC Training

MOM 6
14. 11. 2007
0 views

MOM 6

Warren
03. 10. 2007
0 views

Warren

Program Overview
01. 01. 2008
0 views

Program Overview

Jepordy
06. 11. 2007
0 views

Jepordy

Canon 2006 Market Share Pres
19. 02. 2008
0 views

Canon 2006 Market Share Pres

2005 4160s2 05 rkane
04. 10. 2007
0 views

2005 4160s2 05 rkane

Deen Nutric
06. 03. 2008
0 views

Deen Nutric

z82352 4
10. 03. 2008
0 views

z82352 4

1 Presenting to Decision Makers
12. 03. 2008
0 views

1 Presenting to Decision Makers

9NSFEuropeOfficeGene ral
14. 03. 2008
0 views

9NSFEuropeOfficeGene ral

2 Competitive Advantage
18. 03. 2008
0 views

2 Competitive Advantage

Medieval Presentation revision 1
21. 03. 2008
0 views

Medieval Presentation revision 1

renfrew met obs SO nov06
15. 11. 2007
0 views

renfrew met obs SO nov06

Geography of Grass
07. 04. 2008
0 views

Geography of Grass

November 2005
30. 03. 2008
0 views

November 2005

EAB L 06 1166
28. 11. 2007
0 views

EAB L 06 1166

librarydoc 794
17. 12. 2007
0 views

librarydoc 794

4 InternationalAcademy IBProgram
19. 12. 2007
0 views

4 InternationalAcademy IBProgram

case1
07. 11. 2007
0 views

case1

A guide to Japanese ODA
09. 10. 2007
0 views

A guide to Japanese ODA

tel 00010398
04. 12. 2007
0 views

tel 00010398

www talk
20. 11. 2007
0 views

www talk

Louw 26Mar AM
30. 12. 2007
0 views

Louw 26Mar AM

FUPWebinar121003
29. 12. 2007
0 views

FUPWebinar121003

CCAT Hawaii Overview
01. 10. 2007
0 views

CCAT Hawaii Overview