Schmidt Sebastian, Alanko Jarno N
Department of Computer Science, University of Helsinki, Helsinki, Finland.
Institute of Biology, National University of Sciences, Kiel, Germany.
Res Sq. 2023 Feb 16:rs.3.rs-2581995. doi: 10.21203/rs.3.rs-2581995/v1.
A fundamental operation in computational genomics is to reduce the input sequences to their constituent k-mers. For maximum performance of downstream applications it is important to store the k-mers in small space, while keeping the representation easy and efficient to use (i.e. without k-mer repetitions and in plain text). Recently, heuristics were presented to compute a near-minimum such representation. We present an algorithm to compute a minimum representation in optimal (linear) time and use it to evaluate the existing heuristics. Our algorithm first constructs the de Bruijn graph in linear time and then uses a Eulerian-cycle-based algorithm to compute the minimum representation, in time linear in the size of the output.
计算基因组学中的一个基本操作是将输入序列简化为其组成的k-mer。为了使下游应用程序具有最佳性能，将k-mer存储在小空间中很重要，同时要使表示易于使用且高效（即没有k-mer重复且为纯文本形式）。最近，有人提出了启发式方法来计算这种接近最小的表示。我们提出了一种算法，可在最佳（线性）时间内计算最小表示，并使用它来评估现有的启发式方法。我们的算法首先在线性时间内构建德布鲁因图，然后使用基于欧拉回路的算法来计算最小表示，其时间与输出大小成线性关系。
