香港城市大学:基序检测的随机化算法(PPT讲稿)Randomized Algorithm for Motif Detection
Randomized Algorithm for motif Detection Lusheng Wang Dept of Computer Science City University of Hong Kong Web:http://www.cs.cityu.edu.hk/wlwang e-mail: Iwang @cs. cityu. edu.hk 2021/1/29
2021/1/29 1 Randomized Algorithm for Motif Detection Lusheng Wang Dept. of Computer Science City University of Hong Kong Web: http://www.cs.cityu.edu.hk/~lwang e-mail: lwang@cs.cityu.edu.hk
Outline Review our theoretical results 2. A software for motif detection 3. Other problems we have been working Parametric tools RNA secondary structure comparison Computing translocation distance between genomes 2021/1/29
2021/1/29 2 Outline: 1. Review our theoretical results 2. A software for motif detection 3. Other problems we have been working --Parametric tools RNA secondary structure comparison --Computing translocation distance between genomes
Distinguishing Substring Selection Problem Instance: Given a set B of n, (bad) strings of length at least L, a setG of n,(good) strings, two thresholds db and < Objective: Find a string s such that for each string b E B there exists a substring t of b with lengthl such that d(S,1)≤db and for any string g∈G, (S,g)≥ Bad sequences s: motif Good sequences 2021/1/29
2021/1/29 3 Distinguishing Substring Selection Problem Instance: Given a set B of n1 (bad) strings of length at least L, a set G of n2 (good) strings, two thresholds db and dg ( db < dg ). Objective: Find a string s such that for each string b B there exists a substring t of b with length L such that d(s, t) db and for any string g G, d(s, g) dg . Bad sequences Good sequences s: motif
Applications 1. Finding targets for Potential drugs (T Jiang, C. Trendall, S, Wang, T. Wareham, X. Zhang, 98) (K. Lanctot, M. Li, B Ma, S. Wang, and L. Zhang 1999) bad strings in b are from bacteria --good strings are from Humans find a substring s of length L that is conserved in all bad strings, but not conserved in good strings use s to screen chemicals those selected chemicals can then be tested as potential broad-range antibiotics 2021/1/29
2021/1/29 4 Applications 1. Finding Targets for Potential Drugs (T. Jiang, C. Trendall, S, Wang, T. Wareham, X. Zhang, 98) (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999) -- bad strings in B are from Bacteria. --good strings are from Humans -- find a substring s of length L that is conserved in all bad strings, but not conserved in good strings. -- use s to screen chemicals -- those selected chemicals can then be tested as potential broad-range antibiotics
Applications 2. Creating Diagnostic Probes for Bacterial Infection (T. Brown, G.A. Leonard, E.D. Booth, G. Kneale, 1990) a group of closely related pathogenic bacteria find a substring that occurs in each of the bacterial sequences(with as few substitutions as possible) and does not occurs in the host(Human) 2021/1/29
2021/1/29 5 Applications 2. Creating Diagnostic Probes for Bacterial Infection (T. Brown, G.A. Leonard, E.D. Booth, G. Kneale, 1990) -- a group of closely related pathogenic bacteria -- find a substring that occurs in each of the bacterial sequences (with as few substitutions as possible) and does not occurs in the host (Human)
Applications 3. Creating Universal PCR Primers 4. Creating Unbiased Consensus Sequences 5. Anti-sense Drug design 6. In coding theory(computer science) 2021/1/29
2021/1/29 6 Applications 3. Creating Universal PCR Primers 4. Creating Unbiased Consensus Sequences 5. Anti-sense Drug Design 6. In coding theory (computer science)
Distinguishing string selection Problem Instance: Given a set B of n,(bad) strings of length L, a set G of n2(good)strings of length L, two thresholds db and d Center string Good Strings 2021/1/29
2021/1/29 7 Distinguishing String Selection Problem Instance: Given a set B of n1 (bad) strings of length L, a set G of n2 (good) strings of length L, two thresholds db and dg ( db < dg ). Objective: Find a string s such that for each string b B, d(s, b) db and for any string g G, d(s, g) dg . Bad strings Center string Good Strings
Closest string problem Instance: Given a set B of n strings of length L, and an integer d Objective: Find a string s of length L such that for each string s∈B,a(s,s;)≤d Theorem: Closest string problem is NP-hard. (Lanctot, Li, Ma, Wang, Zhang, 1999) 2021/1/29 8
2021/1/29 8 Closest String Problem Instance: Given a set B of n strings of length L, and an integer d Objective: Find a string s of length L such that for each string si B, d(s, si ) d Theorem: Closest string problem is NP-hard. (Lanctot, Li, Ma, Wang, Zhang, 1999)
Closest Substring Problem Instance: Given a set b of n strings of length at least L and an integer d Objective: Find a string s of length l such that for each string S,E B, there is a substring t; of s,(with length D) such that a(,s)≤d Theorem: Closest substring problem is NP-hard (K. Lanctot, M. Li, B Ma, S. Wang, and L. Zhang 1999) A PTAS was given in M. Li, B Ma, and L. Wang 2000 2021/1/29
2021/1/29 9 Closest Substring Problem Instance: Given a set B of n strings of length at least L, and an integer d Objective: Find a string s of length L such that for each string si B, there is a substring t i of si (with length L) such that d(s, si ) d Theorem: Closest substring problem is NP-hard. (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999) A PTAS was given in M. Li, B. Ma, and L. Wang 2000
Consensus pattern Instance: Given a set B of n strings of different lengths and an integer L Objective: Find a string s of length L and for each string S;E B, find a substring t; of s, such that d(s,t Is minimized Theorem: The consensus pattern problem is NP-hard There is a PTAs for consensus pattern(M Li, B Ma, and L Wang, 1999) 2021/1/29 10
2021/1/29 10 Consensus Pattern Instance: Given a set B of n strings of different lengths, and an integer L, Objective: Find a string s of length L and for each string si B, find a substring t i of si such that n d(s, t i ) i=1 is minimized. Theorem: The consensus pattern problem is NP-hard. There is a PTAs for consensus pattern. (M. Li, B. Ma, and L. Wang, 1999)
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 《数据结构》课程教学资源(PPT课件讲稿)第七章 图及其应用.ppt
- 3D Reconstruction from Images:Image-based Street-side City Modeling.ppt
- 大连理工大学:《计算机网络》课程教学资源(PPT课件讲稿)Chapter 2 应用层 application layer.ppt
- 四川大学:《操作系统 Operating System》课程教学资源(PPT课件讲稿)Chapter 3 Process Description and Control 3.4 Process Control 3.5 Execution of the Operating System 3.6 Unix SVR4 Process Management 3.7 Linux Process management system calls.ppt
- 《数据结构》课程教学资源(PPT课件讲稿)第七章 图 Graph.ppt
- 《数据结构》课程教学资源:实践教学大纲.doc
- 《网络算法学》课程教学资源(PPT课件讲稿)第三章 实现原则.ppt
- 《电脑组装与维护实例教程》教学资源(PPT课件讲稿)第5章 多媒体设备介绍及选购.ppt
- 广西医科大学:《计算机网络 Computer Networking》课程教学资源(PPT课件讲稿)Chapter 02 Network Classification.pptx
- 清华大学:无线网和移动网(PPT课件讲稿)Mobile and wireless network.pptx
- 中国科学技术大学:《计算机体系结构》课程教学资源(PPT课件讲稿)第6章 Data-Level Parallelism in Vector, SIMD, and GPU Architectures.pptx
- 厦门大学:《分布式数据库》课程教学资源(PPT课件讲稿)专题一 分布式数据库介绍.ppt
- 《The C++ Programming Language》课程教学资源(PPT课件讲稿)Lecture 06 OOP with Templates.ppt
- 武汉科技大学中南分校:Windows 2000/XP网络组建与系统管理(系统安装,李燕).ppt
- 电子科技大学:《面向对象程序设计语言C++》课程教学资源(PPT课件讲稿)第五章 构造数据类型.ppt
- 《C语言程序设计》课程电子教案(PPT教学课件)第三章 分支结构.ppt
- 计算机维护与维修(PPT课件讲稿)第十二章 笔记本电脑维护维修.ppt
- 西安电子科技大学:《微机原理与接口技术》课程教学资源(PPT课件讲稿)第四章 汇编语言程序设计(主讲:王晓甜).pptx
- 厦门大学计算机科学系:《大数据技术原理与应用》课程教学资源(PPT课件)第12章 数据可视化.ppt
- 《计算机操作系统》课程教学资源(PPT讲稿)Windows 2003的安全.ppt
- 《计算机组装与维护》课程教学资源(PPT课件讲稿)第9章 BIOS设置(设置BIOS).ppt
- 《Introduction to Java Programming》课程PPT教学课件(Sixth Edition)Chapter 16 Applets and Multimedia.ppt
- 上海交通大学:《挖掘海量数据集 Mining Massive Datasets》课程教学资源(PPT讲稿)Lecture 06 搜索引擎 Search Engines.ppt
- 《计算机系统安全》课程教学资源(PPT课件讲稿)第二章 黑客常用的系统攻击方法.ppt
- 《C语言程序设计》课程教学资源(PPT课件讲稿)第8章 结构体、共用体与枚举类型.ppt
- 香港浸会大学:Introduction to Linux and PC Cluster.ppt
- 南京大学:《计算机图形学》课程教学资源(PPT课件讲稿)第7讲 图元填充与裁剪算法.pptx
- 北京航空航天大学:SimplyDroid - Efficient Event Sequence Simplification for Android Application.pptx
- 《The C++ Programming Language》课程教学资源(PPT课件讲稿)Lecture 04 Object-Based Programming.ppt
- 中国科学技术大学:Linux内核源代码导读(PPT讲稿,陈香兰).ppt
- 《网上开店实务》课程教学资源(PPT讲稿)学习情境3 网店装修.ppt
- 北京大学:《项目成本管理》课程教学资源(PPT课件讲稿)项目范围计划(主讲:周立新).ppt
- 香港中文大学:Achieving Secure and Cooperative Wireless Networks with Trust Modeling and Game Theory.ppt
- MSCIT 5210/MSCBD 5002:Knowledge Discovery and Data Mining:Chapter 4:Data Warehousing, On-line Analytical Processing and Data Cube.ppt
- 《程序设计基础》课程PPT教学课件(C++)第3讲 C++程序控制结构.ppt
- 四川大学:《数据库技术》课程教学资源(PPT课件讲稿)数据库设计.ppt
- 云计算 Cloud Computing(PPT讲稿)MapReduce进阶.ppt
- 《C语言程序设计》课程电子教案(PPT课件讲稿)第7章 用函数实现模块化程序设计.pptx
- 中国科学技术大学:云计算及安全(PPT讲稿)Cloud Computing & Cloud Security.pptx
- 中国科学技术大学:《信号与图像处理基础 Signal and Image Processing》课程教学资源(PPT课件讲稿)数字图像处理基础 Basics of Digital Image Processing.pptx