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.