2023 年中国高校大数据挑战赛 赛题 B DNA 存储中的序列聚类与比对

因此，对于我们设计好的DNA序列，实际生产测序出来后的序列会存在以下差异：

1. 1. 1. 测序后的序列将比原始序列的数量多很多，因为原始序列会被随机扩增成很多条。

1. 1. 1. 测序后的序列相比于原始序列有可能存在错误，包括某个碱基缺失、替换、或添加了某个未知碱基，甚至会出现断链。

针对以上两个特点，目前往往需要对测序后的序列进行聚类与比对。其中聚类指的是将测序序列聚类以判断原始序列有多少条，聚类后相同类的序列定义为一个簇。比对则是指在聚类基础上对一个簇内的序列进行比对进而输出一条最有可能的正确序列。通过聚类与比对将会极大地恢复原始序列的信息，但需要注意由于DNA测序后序列众多，如何高效地进行聚类与比对则是在满足准确率基础上的另一大难点。

“train_reference.txt”是某次合成的目标序列，其中第一行为序号，第二行为序列内容。通过真实合成、测序后读取到的测序序列文件为“train_reads.txt”，我们已经对测序序列进行了分类，该文件第一行为目标序列的序号，第二行为序列内容。

基于赛题提供的数据，自主查阅资料，选择合适的方法完成如下任务：

任务 1：观察数据集“train_reads.txt”、“train_reference.txt”，针对这次合成任务，进行错误率（插入、删除、替换、断链）、拷贝数方面的分析。其中错误率定义为某个碱基发生错误的概率，需要对不同类型的错误率分别进行分析。拷贝数定义为原始序列复制的数量。

任务 2：设计开发一种模型用于对测序后的序列“train_reads.txt”进行聚类， 并根据“train_reads.txt”的标签验证模型准确性。模型主要从两方面评估效果：

1. 聚类后准确性（包括簇的数量以及簇内纯度）、（2）聚类速度（以分钟为单位）。

任务 3：“test_reads.txt”是我们在另一种合成环境下合成的测序文件（与 “train_reads.txt”的目标序列不相同），请用任务 2 所开发的模型对其进行聚类，给出聚类耗时以及“test_reads.txt”的目标序列数量，给出拷贝数分布图。

任务 4：聚类后能否通过比对恢复原始信息也是极为关键的，设计开发一种用于同簇序列的比对模型，该模型可以针对同簇的DNA序列进行比对并输出最有可能正确的目标序列。 请使用该工具对任务 3 中“test_reads.txt”的聚类后序列进行比对，并输出“test_reads.txt”最有可能的目标序列，并分析“test_reads.txt” 的错误率。（请用一个“test_ref.txt”的文件记录“test_reads.txt”的目标序列，文件内序列的形式为：

AAAA…… AAAT…… AATA……

……