DNA存储场景下基于引物索引矩阵的文件高效随机检索方法

Efficient File Random Access Method Based on Primer Index Matrix in DNA Storage Scenarios

DNA分子具有密度高和稳定性的优势,有望成为下一代海量数据存储需求的介质,近年来受到广泛关注。目前将引物作为文件的唯一标识,基于聚合酶链式反应(PCR)扩增技术可实现对DNA池存储文件的随机检索,但对引物与文件之间的分配和映射关系没有进行深入研究,仍然采用随机分配的方式来关联引物与文件,这会导致目标引物序列的查找效率降低,且保存引物与文件的映射关系表会造成大量的数据冗余。为了提供一种高效的硅基计算设备与碳基存储系统的连接桥梁,有效降低存储引物与文件映射关系所带来的数据冗余,该文提出一种基于引物索引矩阵的DNA存储随机检索方法。该方法通过将存储文件集按照文件的不同属性进行划分来构建引物索引矩阵,同时将引物库中的引物按照转换规则转化为有序引物库,最后优化引物与文件之间的映射关系,以实现对文件的高效、多维度检索。实验结果表明,在存储不同规模的文件集时,运用所提算法建立对应的引物索引矩阵,可将引物检索效率提高为常数级时间复杂度,并且存储引物与文件的映射关系所需要的额外存储空间从原来的线性增长优化为对数增长。

DNA molecules have the advantages of high density and stability,and are expected to become the medium for the next generation of massive data storage needs,which has received widespread attention in recent years.Currently,primers are used as the unique identifier for files,and random retrieval of DNA pool storage files can be achieved based on polymerase chain reaction(PCR)amplification technology.However,the allocation and mapping relationship between primers and files have not been thoroughly studied,and random allocation is still used to associate primers and files.This will lead to a decrease in the search efficiency of the target primer sequence,and saving the mapping relationship table between primers and files will cause a lot of data redundancy.In order to provide an efficient connection bridge between silicon-based computing devices and carbon-based storage systems,and effectively reduce the data redundancy caused by storing primer-file mapping relationships,a random retrieval method for DNA storage based on the primer index matrix is proposed in this paper.This method constructs a primer index matrix by dividing the stored file set according to different attributes of the file,and converts the primers in the primer library into an ordered primer library according to conversion rules.Finally,the mapping relationship between primers and files is optimized to achieve efficient and multi-dimensional retrieval during file random retrieval.The experimental results show that when storing file sets of different sizes,the efficiency of primer retrieval is improved to a constant level of time complexity by establishing the corresponding primer index matrix using the proposed algorithm in this paper,and the extra storage space required to store the mapping relationship between primers and files is optimized from linear growth to logarithmic growth.