The Harmonic Indel Distance
Authors: Bob Pepin
Venue: Accepted by TMLR ()

Abstract: This short note introduces the harmonic indel distance (HID), a new distance between strings where the cost of an insertion or deletion is inversely proportional to the string length. We present a closed-form formula and show that the HID is a proper distance metric. Then we perform an experimental comparison of HID to normalized and unnormalized versions of the indel distance on benchmark tasks for biomedical sequence data. We finally show planar embeddings of the benchmark datasets to provide some insights into the geometry of the metric spaces associated with the different distance metrics.

Published in Transactions on Machine Learning Research (11/2024)
The Harmonic Indel Distance
Bob Pepin
bope Red kuu, dk
Deportment of Computer Science University of Copenhagen
Reviewed on OpenReview: https: // openreiiew. net/ per/formm? id= HV9
Abstract
This short note introduces the harmonic indel distance (HID), a new distance between strings where the cost of an insertion or deletion inversely proportional to the string length. We present a closed-form formula and show that the HDD a proper distance metric. Then we perform an experimental comparison of HID normalized and unnormalized versions of the indel distance benchmark tasks for biomedical sequence data. We finally show planar embeddings of the benchmark dalasets to provide some insights into the geometry of the metric spaces associated with the different distance metrics.
1 Introduction and Setting
In this paper, we introduce the harmonic indel distance (HID). The HID distance metric between striings that is normalized in the sense that two long strings that differ by a single symbol are closer to each other than two short strings that differ by a single symbol. Our main technical contribution is Theorem 3.1 which proves the triangle inequality for HID and shows that it indeed defines distance metric between strings.
The HID d(A, B) between two strings A and B is defined by
d(A, B) = 2H (I - H|A| H|B)
(1.1)
where |. denotes string length, Hn >i= 1/i is the harmonic series and les(A. B) denotes the longest common subsequence (LCS) of A and B. We will also use the notation scs(A, B) for the shortest common supersequence (SCS) of two strings.
The paper is structured as follows: in the remainder of this section provide some additional intuition on the definition of the HID, give an overview of related work and briefly comment on the computational complexity. Section proves the triangle inequality. section 4 we first show that HID can be applied to supervised machine learning tasks by two experiments that apply HID to a classification and a regression task. Next, we show that HID is applicable to unsupervised learning by giving an example of a data visualization task. We additionally compare HID to alternative string distances and show that differs from alternative distances some of the tasks. Section wraps up the paper and provides additional suggestions for use cases of the HID.
In order to gain some intuition for the formula (1.1) we can rewrite it as
sccs(A
scs (A
d(A,
Σ
Σ
(1.2)
i=|Ai
j=
using that Isos(A, (A, B) |A| + |B| lcs( A, B)J. The interpretation is as follows: First we insert characters to transform A into scs(A, B), where the cost of each insertion is inversely proportional to the length of the that step. Then we delete characters to transform scs(A, B) into
intermediate string (i in the formula) B, with the cost of deletion again being inversely proportional to the length of the intermediate string (j in the formula) which it is performed.

---

Published in Transactions on Machine Learning Research (11/2024)
Known dissimilarity measures between strings either do not take the length of the strings into account (e.g- Levenshtein distance and its variations) or fail the triangle inequality (e.g. Sørensen Dice similarity), see Chapter 11 in Deza & Deza (2013) for an extensive list. In general, the Steinhaus (or biotope) transform (Deza & Deza, 2013) can be used to transform an unnormalized metric into a normalized metric while preserving the triangle inequality. We will compare the HID to a normalized distance basod on the Steinhaus transform in the experiments in Section 4 and show that it can give different results in some data visualization tasks.
similarity,
Regarding the computational complexity of computing the HID, observe that the formula (1.1) involves only the harmonic scries and the length of the LCS and of the strings A and B. The length of string can be expressed as the length of the LCS of a string with itself. The harmonic series can be precomputed into a lookup table or approximated by the logarithm for large values. The computational complexity of HID is thus equal to the complexity of computing the LCS, which can be computed using dynamic programming algorithms with running time quadratic in the length of the strings (Abboud et al., 2015; Bringmann & Kunnemann, 2015). Recently, algorithms have been developed that approximate the length of the LCS in linear time, which immediately yield linear time approximations of the HID (Bringmann et al., 2023). Other approximations of LCS such as for streaming and spall-space scttings (Cheng et al., 2021) or differentiable approximation of the LCS (Yavuz et al., 2018) immediately yield approximations of the HID with the same properties.
2 Background and related work
The idea behind edit distances it to define the distance between two strings A and B to be the total cost of transforming A into B through a sequence of operations such as insertions, deletions and substitutions of characters. In this work, we consider so-called indel string distances, which are a particular case of edit distances where the possible operations are restricted to insertions and deletions (indels). In particular, a character substitution corresponds to a deletion followed by an insertion.
The most fundamental indel string distance is simply known as the indel distance (ID), see Deza & Deza (2013). Like the HID, the ID quantifies the total cost of transforming a string A into string B using the operations of inserting and deleting characters. The cost of each operation for ID is 1, whereas for HID the cost is inversely proportional to the length of the intermediate string. Comparing HID and ID) therefore allows to isolate the impact of normalizing the cost. The ID can be computed from the LCS using the formula
(A, B) ||| + [B] Ics ())
The Steinhaus transform (biotope transform in Deza & Deza (2013)) is an alternative way of normalizing string distances. The STID is defined by
(d B) dSTID dSTID(A, (A, |A| + |B] + dn (A, B)"
[A) and that (A, BB < 1 for any A, B. This shows in particular that dSTID embeds the space of strings of arbitrary length into a sphere of radius 1. The STID is normalized in the sense that if A is a subsequence of B then
Denoting @ the empty string, note that dsTID (A. 0) 1 for any string A (since dnd 0)
dID(A, B) = [B| - |A] and (A, B) |B In contrast for the HID have dSTID 0) Hiai
that the space of all strings equipped with the STID distance has infinite radius.
The HID is inspired by the contextualized normalized edit distance from de la Higuera & Mico (2008) which requires the computation of shortest paths over all possible edit operations, implemented using a custom dynamic programming algorithm. The contextualized normalized edit distance is then the sum of the costs over the shorlest. path, where the cost. at each step in the path is normalized by the inverse string length at that step.
From (1.2) it is clear that the HID identical the contextualized normalized edit distance restricted insertions and deletions (there is only a single shortest path). Our closed-form formula allows us to reduce
2

---

Published in Transactions on Machine Learning Research (11/2024)
the computational complexity from cubic to quadratic, thereby answering open question posed in de la Higuera & Mico (2008). The L.CS-based formulation also permits the use of existing libraries for computing LCS, available in all major programming languages, and to leverage efficiency improvements made in the algorithms community as described in the next paragraph. We refer to de la Higuera & Mico (2008) for an overview of the related literature up 2008. The only subsequent major development known to the authors is the family of extended edit distances developed Fuad (2014). The basic idea behind the extended edit distances is the addition of penalty term an edit distance which needs be tuned to specifie problem instances, in contrast to the parameter-free definition of the HID.
3 Proof of main result
Theorem 3.1. The harmonic indel distance.
d(A,B) = 21AA Hial - -|B]
defines distance the space of strings. For any three strings A, B, C it satisfies the distance arioms
d(A,B) d(B,A). A),
d) + A and
d(4,C) & d(A, B)+ + d),
Before proving the theorem, we will start with three preliminary lemmaas. In the proofs of the lemmaas, we make extensive use of the observation that if is a subsequence of B, then d(A, H|Bl Hlai which follows immediately from the definition.
Lemma 3.2. For any two strings A and B
d(A, B) = d(A,,ss(A,, B)) + d(scs( B), B).
Proof. First note that, if is a subsequence of B, then d(A, B) = H|BI H|A|- Now, since |scs(A, B) |A| + | - Ics(A, B)| we have
d(A,scs(A B)) d(scs(A, B), B) H scs(A, H||| H sca(A, H|B d(A,
Lemma 3.3. For any three strings A, B,C such that is a subsequence of and is a subsequence of we have
d(A, d(A, d(B,C).
Proof. By the subsequence relations in the assumption the distances simplify and we get.
d(A, d(B. H HAYi + HICI Hin Hic H|^1 d(A,C).
Lemma 3.4. For any two strings A and B have
d(A, B) <
+ d(lcs((, (A,,,,AAAA B).
Proof. By symmetry, we can assume without loss of generality that [A] 2 B|. Now, by direct computation
d(A,B) d(A,,cs(A, d(Ics( (A, B), B)
= -2H -| H|А HiB) (H H (cs(A,B)) (H H (es(A)
22( (1 H|,i) -2(1 H les(A,B))
3

---

Published in Transactions on Machine Learning Research (11/2024)
The first expression in parentheses is sum of [B] [cs((A, B)] terms, all of which are less equal than A/|A| so that
|A|+|
[A),
B Ics( (A, B)
I1 H|
Σ
1/8 S/
A
The second expression in parentheses above is also sum of B lcs(A, B)] terms, all of which are greater equal than 1/IB|, and by our assumption B/| 1/|A|. Therefore
B Σ
B
(cs(A, B)
B
lcs A, B)
H Hes(A.B
1/i2
B
|A|
This shows that
d(A, B) - d(A, (o,,,,, d(lcs(A, B), B) SO
which is the conclusion.
Proof of Theorem 3.1. The symmetry d(A, B) = d(B,A) follows trivially from the definition. So does the "if" direction of the second property. For the only direction, note that d(A, B) can be decomposed into a sum of two positive terms
d(A, B) = (H (ss H1aI) + (H)))++H)ss((AA)) scs(A, - H[B))
so that d(A, B) 0 implies (scs(A, |A| [B] and A = B. To prove the triangle inequality, we use the notation and property scs(A, B,C) scs(A, scs scs (B, C). = scs(scs( A, B), C) and apply in turn Lemmas 3.2, 3.4, 3.3 twice and 3.2 again to obtain
(A,B) + d(B,C)
d(A, scs( A, B)) + d(scs B),
+ + (LB
d(A, ses( (cs((, ()) + ((scs(A, B), scs( (C, C)) +
d(A, scs((s, (,) (scs B, C)
2 d(A, sos( sos(ssssssCC.. d(sos( A, C),C)
d)A,c).
4 Experiments
The purpose of the experiments in this section is to compare the HID to other string distances when applied to machine learning tasks: the indel distance (ID) and the Steinhaus transform indel distance (STID). Note that we do not compare against the contextualized normalized edit distance since it is identical to the HID if we restrict the operations to insertions and deletions as we do in this paper. In addition, the cubic complexity of the normalized edit distance would be prohibitive for our experiments.
We perform experiments on two benchmark tasks for biological sequence regression and classification re- spectively. We also present planar embeddings for each dataset using t-SNE to gain some insight into the geometries of the spaces associated to the different distances. Table 1 presents statistics the datasets used. As our main goal is to evaluate the differences between HID, ID and STID, we do not aim to beat state-of-the-art deep learning models but we do include standard basclines to put our results into perspec- live. We do not claim either that HID is inherently superior to any of the other distances. Each distance embeds the data in a metric space with a different geometry, and the most appropriate geometry depends on the task at hand. Our experiments do show that the different metrics considered result in differences in performance for some but not all tasks and that normalization by string length is beneficial for the two supervised learning tasks considered.
4

---

Published in Transactions on Machine Learning Research (11/2024)
All benchmark experiments used support vector machines with radial basis function kernels based the string metrics described above. The SVM margin as well as the RBF variance hyperparameters were opti- mized using the Tree-structured Parzen Estimator algorithm implemented in the Optuna software (Akiba et al., 2019). We used the SVM implementation from Scikit-Learn (Pedregosa et al., 2011). The hyperpa- rameters used are included in Table 4 in the appendix.
Table 1: Dataset statistics
Number of Sequences
Sequence Length
Dataset
Training
Validation
Test
Min.
Max.
Median
neRNA
25371
6430
13646
42
500
123
FLIP Mixed
22335
2482
3134
20
35213
413
FLIP Human
7287
861
1945
39
34350
477.0
FLIP Human-Cell
5149
643
1366
44
34350
469.0
4.1 Classification
The classification task involves the classification of sequences of non-coding RNA according to their type and uses the Dalasel2 dataset from the benchmark paper Creux el al. (2024). This dataset was chosen because non-coding RNA are some of the shortest biological sequences, and we expect the benefit of the normalization HID to be higher for shorter sequences. The dataset provides training and test splits, and validation was generated by random splitting of the provided training set.
The results are shown in Table 2. We see that the SVMs with HID and STID kernels are competitive with the strongest baseline, which uses recurrent neural network architecture, whereas the SVM with ID kernel underperforms 4 out of the 6 baselines whereas
Table 2: Classification accuracy on ncRNA benchmark
Model
Accuracy (%)
SVM (HID)
97.3
SVM (STID)
97.0
SVM (ID)
90.6
nerna-deep
97.1
MFPred
96.5
RNAGCN
94.7
NCYPred
91.6
nRC
78.3
ncRDense
73.5
Baseline values are taken from Creux el al. (2024)
4.2 Regression
We evaluate the regression performance on the thermostability prediction task from the FLIP benchmark for protein sequences (Dallago el al., 2021). This a challenging beuchmark which includes a carefully selected saiin-validttio-teen split based on biological considerations. The metric adopted by the benchmark is the Spearman correlation cocfficient. The basclines include language models pro-trained on large corpus of sequence data (ESM), the same models trained only on the benchmark training set unttainrri as well CNN and ridge regression model.
5

---

Published in Transactions on Machine Learning Research (11/2024)
Our results are presented together with the baselines in Table 3. The SVMs using normalized distances HID and STID are competitive with all baselines that have not been pre-trained on large corpus of external sequence data, whereas the unnormalized ID SVM only outperforms the weakest baseline.
Table 3: Spearman correlation cocfficient on FLIP thermostability prediction task
Model
Mixed
Human
Human-Cell
Models pretrained on large corpus
ESM-1b (per AA)
0.68
0.71
0.76
ESM-1v (per AA)
0.65
0.77
0.78
Models without pretraining
SVM (HID)
0.42
0.59
0.56
SVM (STID)
0.40
0.59
0.57
SVM (ID)
0.20
0.39
0.40
ESM-untrained (per AA)
0.44
0.44
0.46
ESM-untrained (mean)
0.36
0.48
0.49
CNN
0.34
0.50
0.49
Ridge
0.17
0.15
0.24
Bascline values are taken from Dallago ct al. (2021)
4.3 Metric Embedding
To give some more insights into the different geometries entailed by the HID, STID and ID, we provide t-SNE plots of the training datasets for ncRNA (Figure 1) and FLIP (Figure 2). The objective of t-SNE is to embed a dataset into the plane while keeping the distances in the embedding with the distances in the original space. Each of the distance metrics defines metric space of strings, and expect the (-SNE embedding to reflect much as possible the geometry of the datasel, viewed as points in the string space entailed by the respective distance metric.
consistent possible
For the ncRNA dataset, a visual inspection Figure suggests that all distances result similar geometry, with the normalized distances leading lo a slightly sharper separation for example between red and green classes.
On the other hand, for the FLIP datasets (Figure 2) the different distances lead to clearly different embed- dings. The HID leads to dataset geometry that can be embedded as crescent shape, with lower-valued points concentrating in one end and higher-valued points concentrating in the other end, especially for the Human and Human-Cell datasets.
The embedding for STID still shows concentration of high- and low-value points different regions of the embedding space and recovers the same local structures as the HID embedding. However, it does not show any non-trivial global structures, which might be due to the geometry of the STID metric space being less compatible with Euclidean plane geometry than the HID metric space (recall that the STID space is sphere of radius 1 where all elements are at distance at most from each other). This interpretation is supported by the STID embedding having significantly higher KL divergence than the HID embedding in the t-SNE objective (Table in the appendix).
Finally, the ID produces radially symmetric embedding with regularly spaced patterns that do not show any obvious relation the target value. The regular spacing could be caused by the large number of points that each are at the same integer distance from each other.

---

Published in Transactions on Machine Learning Research (11/2024)
HID
STID
ID
Figure T-SNE plots of ncRNA training dataset using different distance metrics. Colors correspond to different classes. All metrics recover the clusters present in the data with HID and STID obtaining a slightly better separation.
HTD
STID
ID
Mixed
Human
Human- Cell
Figure T-SNE plots of FLIP training datasets using different distance metrics. Colors correspond different target values for thermostability in the regression task. HID shows both global and local structure, STID shows local structure and ID shows little apparent structure.

---

Published in Transactions on Machine Learning Research (11/2024)
5 Discussion
We introduced the harmonic indel distance and showed that it defines distance metric. We showed that the harmonic indel distance outperforms the unnormalized indel distance on two biomedical sequence regression and classification tasks while showing comparable performance to a normalized version of the indel distance. Our experiments on planar embeddings with t-SNE show that HID and STID can in some, but not all, cases result in different planar embeddings. The original motivation for the development of the HID was classification of web browsing histories, which involves significantly shorter data with more variation in the length of sequences, where the lack of normalization in IDD is expected to have datasets where the median length is in
larger impact. It is
striking that there are still such large differences in performance the hundreds of characters, and it could be interesting to evaluate the HID on shorter sequences, for example within social sequence classification. Unfortunately, as of the time of submitting this mamuscript, we were not aware of any suitable benchmark datasets with baselines containing short sequences with high variability in sequence length.
Acknowledgments
The author acknowledges funding received under European Union's Horizon Europe Research and Innovation programme under grant agreement No. 101070408.
References
Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In 2015 TEEE 56th Annual Symposium on Foundations of Computer Science, pp. 59 78, October 2015. doi: 10.1109/FOCS.201555 2011.14 URL https://ieeexplore ieee org/
document/7354388. ISSN: 0272-5428.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A Next- generation Hyperparameter Optimization Framework. In Proceedings of the 25th ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Mining, 2019.
Karl Bringmaan and Marvin Kumnemann. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 79 97, Berkeley, CA, USA, October 2015. IEEE. ISBN 978-1-4673-8191-8, doi: 10.1109/POCS.2055.18 URL http://ieeexploxx ieee. orreeee.o////eeeeeeeeeeeeeeeeeee /dccumeett/355439///
Karl Bringmann, Vincent Cohen-Addad, and Debarati Das. A Linear- Time n0.4 Approxxaatiii for Longest Common Subsequence. ACM Transactions on Algorithmss, 19(1):9:1-9P) 19:2:244 February 2023. ISSN 1549-6325. doi: 10.1145/3568330 URL https: /tte:://dllaae acm orgg/bb/11..145//66333 11445/3568398
Kuan Cheng, Alireza Farhadi, MohammadTTagh Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saced Seddighin, and Yu Zheng. Streaming and Small Space Approximation Algorithms for Edit Dis- tance and Longest. Common Subsequence. In DROPS-IDN/12 Schloss Dagstuhl- Leibmiz-Zentrum für Informatik, 2021. doi: (..2230/LIPlcs... 1CALP.221..1 URL attps://drops dagstuhl. de/ eatitiiss/occmmnn/// 4230/LIPICS ICALP 2021.54.
Constance Creux, Farida Zehraoui, François Radvanyi, and Fariza Tahi. Comparison and benchmark of deep learning methods for nou-coding RNA classification, April 2024. URL https:// http::///wwwbbboi.o...oo/// org/ Section: New Results.
content/10.. 1111//000.1111/2311111 11. 24. 56853663. Pages: 2023.11.22 24..11..4.565586
Christian Dallago, Jody Mou, Kadina E. Johnston, Bruce Wittmann, Nick Bhattacharya, Samuel Goldman, Ali Madani, and Kevin K. Yang. FLIP: Benchmark tasks in fitness landscape inference for proteins. In Thirty-fifth Conference Newrul Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL https://openreriii wttp://wwww....ooooooe/eeeeeaeee
Colin de Higuera and Luisa Mico. A contextual normalised edit distance. In 2008 IEFE 24th International Conference Dala Engineering Workshop, pp. 354-361. IEFF, 2008

---

Published in Transactions on Machine Learning Research (11/2024)
Michel Marie Deza and Elena Deza. Encyclopedia of Distances. Springer, Berlin, Heidelberg, 2013. ISBN 978-3-6442-30957-1 978-3-644-30958-88. doi: 101007/996-3--122306655 URL https://link. springer. 0tt///00.000///77-3-66-----99999
Muhammad Marwan Muhammad Fuad. Parameter-Fres Extended Edit Distance. In International Confer- ence on Data Warehousing and Knowledge Discovery, pp. 465-475. Springer, 2014.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Semih Yavuz, Chung-Cheng Chiu, Patrick Nguyen, and Yonghui Wu. CaLes: Continuously Approximating Longest Common Subsequence for Sequence Level Optimization. In Ellen Riloff, David Chiang, Julia Hockenmaier, and hun'ichi Tsujii (ods.), Proceedings of the 2018 Conference on Empirical Methods Nat- ural Language Processing, pp. 3708 3718, Brussels, Belgium, October 2018. Association for Computational Linguistics. doi: 10.18653/v1/DI5 1406. URL https: //clanttoool org/D18-1406.

---

Published in Transactions on Machine Learning Research (11/2024)
A Experimental Details
The SVMs used in the experiments have regularization parameter C' and the kernels used are k(A, B) = e dist(A, where dist. is either HID ID and with the values for C and 7 given in Table 4.
All t-SNE embeddings used target perplexity of 30 and were run for the number of iterations given in Table 5.
Table 4: Hyperparameters
Dataset
Distance Metric
ncRNA
HID
8.443116755229333
99.5612463103948
ncRNA
STID
9.91793899262693
L.48884487739119
ncRNA
ID
0.000120696026633633631
0.3910622178775564
FLIP Mixed
HID
2.694680159717177
5.303192435762873
FLIP Mixed
STID
3. 5.4533354922866195
L.696222220638886
FLIP Mixed
ID
2.018893677188889
FLIP Human
HID
3.0711811333241188
8.9720944031636633
FLIP Human
STID
2.472937362472116
FLIP Human
ID
0.00010361 1000003311284493441 128449343376
0.6548096783307111
FLIP Human- Cell
HID
2.211198503980429
5.99431
FLIP Human-Coll
STID
4. 4.758786455584244
98-488332386599603
FLIP
Human- Cell
ID
0.0001011125347007622229
0.02074221663631333
Table 5: Hyperparameters and statistics for t-SNE plots
Dataset
Distance Metric
Iterations
KL Divergence
neRNA
HID
2048
1.876777
ncRNA
STID
2048
1.889551
ncRNA
ID
2048
2.277497
FLIP Mixed
HID
8192
2.349853
FLIP Mixed
STID
8192
2.582142
FLIP Mixed
ID
8192
3.670377
FLIP Human
HID
8192
1.968790
FLIP Human
STID
8192
2.299917
FLIP Human
ID
8192
3.546993
FLIP Human-Cell
HID
8192
1.891862
FLIP Human-Cell
STID
8192
2,250279
FLIP Human-Cas
ID
8192
3.459189
10

---

Published in Transactions on Machine Learning Research (11/2024)
A.1 Effect of perplexity parameter t-SNE plots
To validate that the I-SNE plots in the main paper are represenlative, we here show the plots resulting from parameter sweep of the perplexity parameter from 2-2 to 2 for the Human Cell dataset from FLIP. The plots show that our observation that HID preserves more global structure the t-SNE plots than STID is robust to different parameter values. All embeddings were run to convergence.
The resulting plots are included as separate file in the supplementary material.
11


Reviews:
[{"review_id": "G5P8cMJqNz", "reviewer": "Reviewer_SHHu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Authors derive novel metric between strings\n\nWeaknesses:\n\n- Authors do not motivate why a different string metric is needed and empirical evaluation is not convincing\n    - The empirical results show marginal benefit over other metric (STID) and other existing methods\n    - The paper would benefit from more exploration into the specific settings in which HID has improved performance over STID. e.g. in the empirical evals, the authors could show whether HID does have higher accuracy for shorter strings, as suggested by the Intro, or for ncRNAs/proteins of a specific type?\n- Metric embedding section is not rigorous and does not provide any insight\n    - I do not think it is that useful to look at t-sne embeddings. These embeddings are known to be sensitive to hyperparameters and not properly reflect distances (e.g. Chari and Pachter, Plos Comp Bio 2023, among many other papers). These embeddings in Figs 1/2 just show that the HID is different, and do not provide any insight into why the HID is different (or better) than the STID or ID metrics\n- More theoretical characterization is necessary\n    - The authors make a small comment about the HID corresponding to a restricted version of the normalized edit distance from de la Higuera & Mico (2008). This should be described in greater detail.\n        - It would also be useful to describe the *weighted* HID, where certain edits are penalized more than others. Such weighted distances are often used to quantify the distance between DNA motifs (eg Gupta et al, Genome Biol 2007)\n    - Moreover, the authors could give numerical examples (e.g. on simulated data) showing how the HID and STID differ for short strings versus larger strings\n    - The HID also seems non-ideal for very long strings, eg genome-length strings, since one would presumably need many bits to store 1/i for very large i. It would be useful to see some discussion on how to represent the HID for long strings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper the authors describe a new similarity between two strings, called the harmonic indel distance. Their metric is similar to edit distance but penalizes edits less for larger strings. The authors prove their similarity is a metric and show some usecases for it on classifying ncRNAs and thermostability prediction for proteins.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see a modified manuscript that address the major weaknesses I described above. In particular to secure my recommendation for acceptance, I would like to see: (1) more evaluation on real data showing how/why the HID improves over the STID/ID; (2) the metric embedding section should be removed; and (3) more discussion on theoretical properties of HID, in particular describing how to compute the weighted HID.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fpDkc8mA31", "reviewer": "Reviewer_kjbY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strenghts\n- Sound paper, providing theoretical proofs for the distance metric as well as insightful empirical experiments\n- Sufficiently different to related works, extending prior works on normalized edit distances with a novel grounding based on the harmonic series.\n\n# Weaknesses\n- The embeddings experiments could benefit from varying the used perplexity of 30 or at least better discussing why it is sufficient to not do so. The question remains open if the global structure might be better preserved for the other metrics when using another perplexity parameter. \n- Empirical added value compared to existing normalized edit distances is rather low\n- Not clear from the paper why the empirical evaluation does not include the referenced work of contextualized normalized edit distance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces the Harmonic indel distance (HID), which is a normalized version of the edit/indel distance. HID builds on the harmonic series and has low compuational complexity, reducible to calculating the longest common substring between the the two input strings.\n\nThe paper theoretically proves that HID is a distance metric and additionally provides empirical experiments for biological sequence regression and classification, as well as an analysis for trained embeddings using t-SNE. The used datasets are \"Dataset2\" from a non-coding RNA classification benchmark (ncRNA) and the FLIP benchmark. The machine learning model is a SVM with radial basis function kernels.  HID is compared to the Steinhaus indel distance and indel distance, as well as established competitors of other approaches for the respective tasks.\n\nThe results show that HID for SVM training is superior or at least competitive in the classification and regression tasks. It specifically outperfors the indel distance for classification, while being roughly similar in performance to the Steinhaus variant. The resulting embeddings show to also preserve the global structure of the dataset better than the competitors in the given experiment.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Please provide a dedicated related work or background section with edit distance, contextualized normalized edit distance, Steinhaus transform indel distance, ... . While the introduction has a short paragraph on related works, it does not clarify differences to direct competitors.\n* Please provide a more detailed discussion why a single perplexity parameter is sufficient to claim that global structure can be better preserved using HID.\n* Please provide a reference for the used and mentioned Optuna software as well as the Scikit-learn library.\n* Please provide a motivation why an empirical evaluation against the contextualized normalized edit distance is not needed or add it to the paper. The paper already mentiones downsides of the work (i.e., needing to calculate shortest paths), but it cannot be ruled out that there might be predictive performance differences for downstream tasks.", "broader_impact_concerns": "Broader impact concerns are not available in the paper, but it is deemed ok that way. The paper proposes a novel distance metrics suitable for string representations, which can be applied broadly. The proposed distance metrics does not introduce any obvious biases which might have general manipulative/negative repercussions.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CEGP6lsid2", "reviewer": "Reviewer_5NUi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed HID method is a contribution to indel distance metrics. HID satisfies the distance axioms and has comparable performance with mainstream methods like STID.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel normalized string indel distance metric called the Harmonic Indel Distance (HID). In HID, the cost of insertion or deletion is inversely proportional to the string length. The authors demonstrate that HID meets the required distance axioms. They then compare HID with the normalized metric STID and the unnormalized metric ID using biomedical datasets. Lastly, the authors illustrate the planar embeddings of the benchmark datasets to explore the geometric properties of HID, STID, and ID.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Regarding the special contribution of HID, the performance of HID seems to be the same as STID according to the recorded experiment results. \n\n2. The authors mention that they do not aim to beat SOTA method but to evaluate the differences between HID, STID, and ID. However, the authors only investigate the difference in t-SNE embedding shape. According to prior work[1], the global structure of the t-SNE plot may vary according to different parameter settings. Therefore I would suggest a deeper investigation into this question.\n\n[1] Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian. How to Use t-SNE Effectively. https://distill.pub/2016/misread-tsne/", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All of the reviewers agree the correctness and originality of the paper. The applications provided in the paper are also great. Please update the manuscript based on the feedback from the reviewers during the discussion phase for the camera ready.
Decision: Accept (poster)