AF: Small: Reconstructing Mixtures of DNA Sequences from High-Throughput Sequencing Data

在基因组学和个性化医学的一系列问题中，准确地重建存在于异质混合物中的不同的核苷酸序列是至关重要的。例子包括病毒准种重建、免疫细胞图谱绘制和单倍型。虽然高通量DNA测序的最新进展使人们能够负担得起遗传变异的研究，但测序平台的技术限制以及混合物中序列的潜在不均匀频率使得对不同混合物的分析成为一项具有挑战性和计算密集型的任务。本研究旨在开发快速而准确的算法来重建和估计不同混合物中的序列，以帮助药物基因组学和个性化药物的从业者。该项目的重点是促进多样性，跨学科传播新的跨学科研究，以及丰富参与的工程学学生的教育经验。该项目的具体目标包括：首先，设计和分析矩阵因式分解方法，以准确和有效地重建存在于不同混合物中的不同序列，并估计其频率。在该框架中，序列重构被描述为分解结构化的、部分观察到的低秩阵的问题，并通过利用高通量测序数据的显著特征来有效地解决该问题。第二，开发了一种方法，用于分析通过高通量测序手段在时间上采样的动态演变的序列混合物。这一研究方向将导致新的序列重建方法，能够跟踪序列随时间的演变并准确识别其频率。第三个也是最终目标是开发针对特定序列多样性分析问题的算法解决方案，充分利用各个应用程序的结构特征，从而实现卓越的性能。

In a wide range of problems in genomics and personalized medicine, it is of critical importance to accurately reconstruct distinct nucleotide sequences present in a heterogeneous mixture. Examples include viral quasispecies reconstruction, mapping repertoire of immune cells, and haplotyping. While recent advancements in high-throughput DNA sequencing have enabled affordable studies of genetic variations, technological limitations of sequencing platforms as well as potentially non-uniform frequencies of the sequences in a mixture render the analysis of heterogeneous mixtures a challenging and computationally intensive task.This research aims to develop fast and accurate algorithms for reconstruction and frequency estimation of sequences in diverse mixtures that will assist practitioners in pharmacogenomics and personalized medicine. The project includes a focus on fostering diversity, dissemination of new interdisciplinary research across disciplines, and enrichment of the educational experience of participating engineering students.Specific goals of the project include: First, the design and analysis of matrix factorization methods for accurate and efficient reconstruction of distinct sequences present in a heterogeneous mixture and for estimation of their frequencies. In the proposed framework, sequence reconstruction is formulated as the problem of factorizing structured, partially observed low-rank matrices and efficiently solved by exploiting salient features of high-throughput sequencing data. Second, the development of a methodology for the analysis of dynamically evolving mixtures of sequences temporally sampled by means of high-throughput sequencing. This research thrust will lead to novel sequence reconstruction methods capable of tracking the evolution of sequences over time and accurate identification of their frequencies. The third and final goal is the development of algorithmic solutions to specific sequence diversity analysis problems that fully exploit structural features of the respective applications and thus enable superior performance.