III: Small: RUI: Efficient Search, Comparison, and Annotation for Biological Sequences

III：小：RUI：生物序列的高效搜索、比较和注释

• 批准号: 1528027
• 负责人: Abdullah Arslan
• 金额: $ 7.68万
• 依托单位: Texas A&M University-Commerce
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1528027&HistoricalAwards=false
• 关键词: III; Small; RUI; Efficient; Search

This project aims to develop fast algorithms for searching, comparing, and annotating protein and RNA sequences. Regular expression matching is commonly used in UNIX-based systems for searching texts, and in PROSITE website for searching patterns in protein sequences. Context free grammar matching is used in searching RNA sequences. Annotating biological sequences (DNA, protein, and RNA sequences) using regular expression and context free grammar described motifs is an important application available in many public databases, websites, and software tools (e.g. PROSITE, Locomotif). The results of the proposed project will be helpful for programmers who develop pattern matching and parsing applications which would benefit from fast algorithms for searching and annotating sequences. An example of such an application outside bioinformatics is parsing with multiple context free grammars, which is used in natural language processing and program compiling. There will be strong student involvement during the entire project. As implementations become complete, students will help the PI present these implementations, and make them available for use in project web pages. This project involves fundamental computer science theory with applications in bioinformatics. It will yield new knowledge and case study results in automata and formal languages which are essential parts of the computer science curriculum. It will also help involved students master these topics.This project will develop algorithms for searching, comparing and annotating protein and RNA sequences by using (1) Seed-based matching: For finding an approximate match to a given sequence, popular alignment and search tool BLAST locates first an exact match of fixed length region (seed) and extends the matching region around the seed. This project generalizes the use of seeds in novel ways to pattern matching and annotation problems for regular expression and context free grammar described patterns. Initial results indicate that the proposed seed-based approach finds matches about 2.5 times faster than UNIX GREP utility on 2MB texts; (2) Suffix tree/array-based matching: For the annotation problem with bounded-length patterns over fixed alphabets, this project proposes using a suffix tree (or a suffix array) extended with additional information in order to identify from a candidate set, a regular expression or a context free grammar that generates a given string; and (3) A new representation for RNA: This project proposes a new RNA secondary structure representation in which two-dimensional structure information is embedded in the sequence with desirable features. For RNA sequences, the proposed new algorithms will exploit the advantages of this representation for fast RNA search, annotation, and comparison (of multiple RNAs to locate common substructures). Seed-based search and RNA comparison problems (using the new representation) will be addressed in the first year, and annotation problems in the second year as sequence annotation will make use of the results from the first year. The project will create experimental databases from publicly available databases such as PROSITE, Rfam, RNA STRAND, rCAD (in particular RNA sequences in .bpseq files) for the purpose of explaining and showing the results of the developed algorithms. Every semester, during the project, students will be involved in developing, implementing, testing new algorithms, user interfaces, and relevant support tools.

该项目旨在开发用于搜索、比较和注释蛋白质和 RNA 序列的快速算法。正则表达式匹配通常在基于 UNIX 的系统中用于搜索文本，并在 PROSITE 网站中用于搜索蛋白质序列中的模式。上下文无关语法匹配用于搜索 RNA 序列。使用正则表达式和上下文无关语法描述的基序注释生物序列（DNA、蛋白质和 RNA 序列）是许多公共数据库、网站和软件工具（例如 PROSITE、Locomotif）中可用的重要应用。拟议项目的结果将对开发模式匹配和解析应用程序的程序员有所帮助，这些应用程序将从用于搜索和注释序列的快速算法中受益。生物信息学之外的此类应用的一个示例是使用多个上下文无关语法进行解析，该语法用于自然语言处理和程序编译。整个项目期间将有大量学生参与。当实施完成后，学生将帮助 PI 展示这些实施，并使它们可在项目网页中使用。该项目涉及基础计算机科学理论及其在生物信息学中的应用。它将产生自动机和形式语言方面的新知识和案例研究结果，这是计算机科学课程的重要组成部分。它还将帮助相关学生掌握这些主题。该项目将开发搜索、比较和注释蛋白质和 RNA 序列的算法，方法是使用 (1) 基于种子的匹配：为了找到给定序列的近似匹配，流行的比对和搜索工具 BLAST 首先定位固定长度区域（种子）的精确匹配，并将匹配区域扩展到种子周围。该项目以新颖的方式概括了种子的使用，以解决正则表达式和上下文无关语法描述模式的模式匹配和注释问题。初步结果表明，所提出的基于种子的方法在 2MB 文本上查找匹配项的速度比 UNIX GREP 实用程序快约 2.5 倍； (2) 基于后缀树/数组的匹配：对于固定字母表上有界长度模式的注释问题，该项目建议使用附加信息扩展的后缀树（或后缀数组），以便从候选集中识别生成给定字符串的正则表达式或上下文无关语法； （3）RNA的新表示：该项目提出了一种新的RNA二级结构表示，其中二维结构信息嵌入到具有所需特征的序列中。对于 RNA 序列，所提出的新算法将利用这种表示的优势进行快速 RNA 搜索、注释和比较（多个 RNA 来定位共同的子结构）。基于种子的搜索和 RNA 比较问题（使用新的表示）将在第一年解决，第二年的注释问题作为序列注释将利用第一年的结果。该项目将从 PROSITE、Rfam、RNA STRAND、rCAD（特别是 .bpseq 文件中的 RNA 序列）等公开数据库创建实验数据库，以解释和显示所开发算法的结果。每个学期，在项目期间，学生将参与开发、实施、测试新算法、用户界面和相关支持工具。