Scaling Flow Decomposition to Multi-Sample Multiassembly and Comparison

从短序列数据中组装完整的RNA和DNA序列是生物学中的一个基本计算问题。该项目的目标是开发最先进的算法方法，以更好地组装序列，并保证计算效率和所产生的组装的质量。我们将在生物数据集上评估这些计算方法，并开发最有前途的软件工具，这些工具有很好的文档，便于生物研究界的任何人使用。该项目将为蒙大拿州立大学(MSU)的两名博士生提供支持和培训，并可能通过蒙大拿州立大学(MSU)旨在吸引本科生参与研究的现有项目以及计算学院的新REU项目，让本科生参与研究。此外，还为当地社区的K-12学生计划了外展活动。该项目的技术重点是改进RNA和DNA多重组装的计算方法和算法--来自下一代测序读数的多个相关但不同的基因序列的组装。多重组装对于生物学研究中的许多任务都是必不可少的，从组装基因转录本来表征基因功能，到在进化的种群中组装病毒变体。虽然这个领域中有现有的工具，但它们通常是围绕着启发式方法构建的，这些方法不一定保证找到最优解决方案。这个项目的目标是围绕问题的显式表述和能够找到最优解的精确计算方法。具体目标包括为流量分解问题开发可扩展的方法并确定解决方案的“安全”属性，调整方法以应对较新的技术，如成对端和长时间读取以及数据中的不确定性，以及比较和关联来自多个样本的数据。该项目的结果将在网站“www.cs.montana.edu/MultiAssembly”上公布。该项目由生物基础设施部(DBI)和既定的激励竞争研究计划(EPSCoR)共同资助。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The assembly of full RNA and DNA sequences from short sequence data is a fundamental computational problem in biology. The goals of this project are to develop state-of-the-art algorithmic approaches to better assemble sequences with guarantees on computational efficiency and the quality of the assemblies produced. We will evaluate these computational methods on biological datasets and develop the most promising software tools that are well-documented and easy to use by anyone in the biological research community. The project will provide support and training for two PhD students at Montana State University (MSU) and will also potentially involve undergraduate students in research, both through existing programs at MSU designed to engage undergraduate students in research, as well as through a new REU program in the School of Computing. Additionally, outreach activities are planned for K-12 students in the local community.The technical focus of the project is to advance computational methods and algorithms for both RNA and DNA multiassembly -- the assembly of multiple related but different genetic sequences from next-generation sequencing reads. Multiassembly is essential for many tasks in biological research, from the assembly of gene transcripts to characterize gene function to the assembly of viral variants in an evolving population. While there are existing tools in this space, they are often built around heuristic methods that do not necessarily guarantee an optimal solution is found. The objectives of this project are centered around explicit formulations of the problems and on exact computational methods that can find optimal solutions. Specific aims include developing scalable methods for flow decomposition problems and identifying “safe” properties of the solutions, adapting methods to cope with newer technologies such as paired-end and long reads as well as uncertainty in data, and comparing and relating data from multiple samples. Result of the project will be found on the website "www.cs.montana.edu/multiassembly". The project is jointly funded by Division of Biological Infrastructure (DBI) and the Established Program to Stimulate Competitive Research (EPSCoR).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.