General Neural Embedding for Sequence Distance Approximation

Sequence distance computation is a critical and fundamental task in many fields, such as bioinformatics, and time series analysis. Traditional functions for computing the distance between sequences are often based on dynamic programming to find a globally optimal alignment, which has quadratic complexity and is difficult to parallelize, thus limiting their application in large-scale datasets with long sequences. To solve this problem, various fields have designed some specialized models to approximate these distance functions inspired by deep representation learning, i.e., projecting the sequence into a geometric embedding space through an embedding function, so that the distance between sequences can be approximated by the distance in the high-dimensional embedding space, thereby reducing the quadratic complexity to linear. However, we note that even though the element types in sequence and distance functions are different across various fields, the core problem that needs to be solved remains the same. In this paper, we attempt to unify the sequence distance computation approximation from various fields and propose GnesDA. Specifically, we first unify the input representation of sequences in which the element type is the symbol and numeric values. We then encode the sequence using a convolutional block and a Transformer block sequentially, which can effectively capture local patterns and long dependencies respectively. Extensive experiments on four distance functions as well as four large-scale real-world datasets demonstrate that GnesDA achieves state-of-the-art in terms of both versatility and effectiveness. For the task of similarity retrieval, GnesDA can improve the edit distance, NW distance, DTW, and EDR by an average of 10.55%, 6.67%, 4.51%, and 12.00% on all metrics.