Toward the regularization of E value from BLAST similarity search into a dissimilarity measure as distance function, and the metrication of protein sequence space Authors: Boryeu Mao Published: 2026 ABSTRACT AbstractSequence matching algorithms such as BLAST and FASTA have been widely used in searching for evolutionary origin and biological functions of newly discovered nucleic acid and protein sequences. As parts of these search tools, alignment scores and E values are useful indicators of the quality of search results (and the relevance of the matches) from querying a database of annotated sequences, whereby a high alignment score (and inversely a low E value) reflects significant similarity between the query and the subject (target) sequences. For cross-comparison of results from sufficiently different queries, however, the interpretation of alignment score as a similarity measure and E value a dissimilarity measure becomes somewhat nuanced, and prompts herein a judicious distinction of different types of similarity. Via a simulated formulation, we show that an adjustment of E value to account for self-matching of query and subject sequences corrects for certain ostensibly anomalous similarity comparisons, resulting in “regularized” dissimilarity and similarity measures that would be more appropriate for cross-comparisons, as well as database applications, such as all-on-all sequence alignment or selection of diverse subsets. In actual practice, the “regularization” of E value dissimilarity improves clustering and subset selection. While both E value and the “regularized” E value share two of the four axiomatic properties of a metric space, positivity, and symmetry, the latter E value further becomes reflexive and meets the condition of triangle inequality, the remaining two axioms, thus itself an appropriate distance function for metricating protein sequence space.Keywords: protein sequence comparison, BLAST similarity search, E value, similarity and dissimilarity measures for protein sequence space, relaxed triangle inequality and generalized metric space Introduction For nascent nucleic acid and protein sequences, often the first step in the identification of the evolutionary origin and the biological function is the search for similar sequences in annotated bioinformatics databases. Sequence matching tools such as BLAST [1–4] evaluate molecular similarity for proteins and nucleic acids with algorithms for aligning sequences and computing alignment scores [4, 5] according to the extent of amino acid residue or nucleic acid base matches and mismatches along the length of the sequences, as well as any gaps that may help improve the overall alignment. Calculated from the alignment score for a query-subject sequence pair, an expected value, or E value [2, 5–7], is a statistical estimate of the expected number of chance matches with better alignment, a useful indicator of the significance and relative quality of search results from screening the given query sequence against a relevant, annotated bioinformatics database. The exponential relationship between the alignment score S and the E value Eval, in the functional form of Eval∼ e^(-S) [2, 5], is an inverse relationship in the general form of an exponential decay function for transformation between a similarity measure and its dissimilarity counterpart, and vice versa [8, 9]. The comparison of S and Eval for an example set of five sequences, listed in Table 1(a) and derived from protein domain d1dlwa_ in the hierarchical protein structure database SCOP [10, 11], are shown in Table 1(b). For query sequence seq.1, the alignment score decreases as the subject (target) sequence becomes less similar (progressively shorter), from seq.z to seq.b, and to seq.az, with concomitant increases of E value. Relative to the seq.1 series, the alignment score of the subject/query pair of seq.az/a is higher than seq.az/1 as expected (since seq.a is closer to seq.az than seq.1 is), but somewhat unexpectedly falls short of seq.b/1, despite the fact that with only one substitution the seq.az/a pair might have been considered to be more similar than seq.b/1, for which there is a gap and a length deficit of 16 residues in the global alignment. This apparent contradiction, that a higher similarity is reflected in a higher score in one instance (seq.b/1 over az/1 with a score of 480.0 over 361.0) but paradoxically in a lower score in another (seq.az/a over b/1 and yet with a score of 407.0 below 480.0), is partly semantic, and largely resolvable with the recognition of two distinctive types of similarity: (i) the alignment score-based similarity which is strongly influenced by the extent of pairwise matched positions between query and subject, and (ii) a “regularized” form of similarity unified across queries, with which seq.az/a would otherwise score higher than seq.b/1. A corollary of the above is that, while the alignment-score similarity (and the inverse dissimilarity) is completely satisfactory for evaluating matches from a single, or closely related queries, a suitably defined “regularized” similarity measure may be more appropriate in order for matches from sufficiently different queries to be directly cross-compared more efficaciously. This putative “regularized” similarity and the related dissimilarity measure may be expected to be equally suitable for comparing single query matches as well as those from disparate queries such as the all-on-all sequence matching within a database for discovering homologous sequences, detecting gene families, constructing phylogenetic trees [12, 13], clustering sequences for diversity selections [14], or constructing protein families [15, 16]. Table 1Amino acid sequences and their similarity and dissimilarity scores for Case study #1.(a)Sequence name, sAmino acid sequence, 𝕤Notes1a slfeqlggqaavqavtaqfyaniqadatvatffngidmpnqtnktaaflc aalggpnawtgrnlkevhanmgvsnaqfttvighlrsaltgagvaaalveqtvavaetvrgdvvtv SCOP domain d1dlwa_ (length 116 residues) z slfeqlggqaavqavtaqfyaniqadatvatffngidmpnqtnktaaflc aalggpnawtgrnlkevhanmgvsnaqfttvighlrsaltgagvaaalve qtvavaetvrgdvvqv seq.1 with t-to-q substitution at position 115 b slfeqlggqaavqavtaqfyaniqadatvatffngidmpnqtnktaaflc aalggpnawtgrnlkevhanmgvsnaqfttvighlrsaltgagvaaalve residues 1–100 of seq.1 az slfeqlggqaavqavtaqfyaniqadatvatffngidmpnqtnktaaflc aalggpnawtgrnlkevhanmgvsnaqftq seq.a with t-to-q substitution at position 80 a slfeqlggqaavqavtaqfyaniqadatvatffngidmpnqtnktaaflc aalggpnawtgrnlkevhanmgvsnaqftt residues 1–80 of seq.1(b)SubjectQueryAlignment score (similarity)E value (dissimilarity) z 1 574.01.313e-58 b 1 480.01.043e-47 az 1 361.06.560e-34 az a 407.02.097e-39(a) Amino acid sequence of SCOP domain d1dlwa_, seq.1, and four derivative sequences. seq.1 is fetched with Biopython subpackage Bio.SCOP (an interface to SCOP database), class and method Scop.getDomains()[1].(b) Alignment scores and E values (calculated according to M.1 and M.2) for the first four subject/query pairs in Table 2. aSequence of domain id 1 (dom.1) doubles as the sequence name. Amino acid sequences and their similarity and dissimilarity scores for Case study #1. (a) Amino acid sequence of SCOP domain d1dlwa_, seq.1, and four derivative sequences. seq.1 is fetched with Biopython subpackage Bio.SCOP (an interface to SCOP database), class and method Scop.getDomains()[1]. (b) Alignment scores and E values (calculated according to M.1 and M.2) for the first four subject/query pairs in Table 2. aSequence of domain id 1 (dom.1) doubles as the sequence name. In the Results and Discussion section, investigations of the five protein sequences in Table 1(a) comprise Case study #1 for illustrating the ostensible anomaly, and for motivating the regularization of E value for resolving the anomaly. For facilitating calculations on sequence sets in the Case studies, a stand-alone system of procedures was prepared for simulating the E value computation in BLAST searches, which is described in the Methods section with details on parameters for the calculation of alignment scores and E values. Formal properties of the sequence length-adjusted, “regularized” E value are then examined in Case studies #2 - #4, on sequences of SCOP structure domains, and their parametric dependency noted as appropriate. Also in the Methods section, relevant formulae, expressions and systems information are collected and grouped into subsections A to H. Key items are labeled in bold. Results and discussion Case study #1, five sequences derived from SCOP domain d1dlwa_ (Table 1(a)) SCOP domain d1dlwa_ is fetched with Biopython package Bio.SCOP, class and method Scop.getDomains()[1] from the database (see Methods section). Alignment score S and E value Eval, calculated respectively from expressions M.1 and M.2 for four relevant pairs (column 1 of Table 2, rows 1–4), are shown in columns 2 and 3. Against the series of pairwise alignments for query seq.1 (rows 1–3), the alignment score S for the subject/query pair seq.az/a (row 4, same length with one substitution) is higher than that of seq.az/1 (row 3, length deficit of 36 residues), as expected. The alignment score of 407.0, as a similarity measure for the seq.az/a pair, is lower than 480.0 for the seq.b/1 pair, however, contrary to the expectation that the single substitution in the seq.az/a pair presumably should imply a higher degree of similarity (and thus a higher score) than the 16-residue length deficit in the seq.b/1 pair. Table 2Regularization of similarity and dissimilarity scores for sequences in Table 1.s/q (subject, query)S(𝕤, 𝕢) (“bits” similarity)Eval(𝕤, 𝕢) (“bits” dissimilarity)Evalb(𝕤, 𝕢)Êval(𝕤, 𝕢) (“regularized” dissim.)Ŝ(𝕤, 𝕢) (“regularized” sim.) z/1 574.01.313e-58 [1.332e-64]2.645e-59 1.602 [1.752] 0.755 b/1 480.01.043e-47 [1.989e-52]4.793e-5516.895 (16.747) [18.906]1.722e-07 (1.997e-07) az/1 361.06.560e-34 [2.452e-37]1.057e-4936.364 (35.993) [39.964]1.611e-16 (2.336e-16) az/a 407.0 2.097e-39 [1.384e-43]4.226e-40 1.602 [1.752] 0.755 Self-matching 1/1 580.02.645e-592.645e-590.01.0 b/b 506.08.684e-518.684e-510.01.0 a/a 413.04.225e-404.225e-400.01.0Triangle inequality z/a – 9.116e-35 – 34.391 [38.212]– z/az – 4.524e-34 – 35.993 [39.964]– a/1 –1.322e-34–34.762 (34.391) [38.212]– b/z –1.043e-47–16.895 (16.747)–Rows 1 to 4: regularization of alignment score and E value (columns 2 and 3) to corresponding dissimilarity and similarity measures (columns 5 and 6). Values in bold face are the smaller of two dissimilarity/similarity scores when subject and query exchange positions. Rows 5–7: self-matching alignment scores and E values. Rows 8–9 (along with row 4), for checking triangle inequality of dissimilarity: 9.116e-35 + 2.097e-39 ≈ 9.116e-35 < 4.524e-34 for Eval, and 34.391 + 1.602 = 35.993 for Êval, and similarly for row 10 along with rows 3 and 4. Varying parameters in the calculation of alignment score introduces relatively small changes in numerical values but not the overall relationships: for example Eval’s and Êval’s for the gap penalty open_gap_score of −13.0 (λ of 0.292 and K of 0.071) are shown in square brackets in columns 3 and 5, and for substitution matrices BLOSUM90 and PAM250 (data not shown).NB. (1) Unlike those among seq.{1,z,az,a} above, the triangle inequality holds for the triplet seq.{1,b,z}, rows 1, 2, and 11, column 3, for which the Eval-Êval relationship is monotonic (the initial part of the curve in blue, third curve from the top and marked with squares, in Fig. 1a). (2) For the az/a pair, the recovery of any potential false negatives for Eval as a dissimilarity measure appears as breaks in the monotonicity of the Eval-Êval curve. Regularization of similarity and dissimilarity scores for sequences in Table 1. Rows 1 to 4: regularization of alignment score and E value (columns 2 and 3) to corresponding dissimilarity and similarity measures (columns 5 and 6). Values in bold face are the smaller of two dissimilarity/similarity scores when subject and query exchange positions. Rows 5–7: self-matching alignment scores and E values. Rows 8–9 (along with row 4), for checking triangle inequality of dissimilarity: 9.116e-35 + 2.097e-39 ≈ 9.116e-35 < 4.524e-34 for Eval, and 34.391 + 1.602 = 35.993 for Êval, and similarly for row 10 along with rows 3 and 4. Varying parameters in the calculation of alignment score introduces relatively small changes in numerical values but not the overall relationships: for example Eval’s and Êval’s for the gap penalty open_gap_score of −13.0 (λ of 0.292 and K of 0.071) are shown in square brackets in columns 3 and 5, and for substitution matrices BLOSUM90 and PAM250 (data not shown). NB. (1) Unlike those among seq.{1,z,az,a} above, the triangle inequality holds for the triplet seq.{1,b,z}, rows 1, 2, and 11, column 3, for which the Eval-Êval relationship is monotonic (the initial part of the curve in blue, third curve from the top and marked with squares, in Fig. 1a). (2) For the az/a pair, the recovery of any potential false negatives for Eval as a dissimilarity measure appears as breaks in the monotonicity of the Eval-Êval curve. Rather than a completely different similarity measure, either within or possibly without the current E value framework [17–19], the apparent contradiction (or at least an inconsistency, semantic or otherwise) may be resolved instead with the recognition, and the reconciliation and regularization, of two distinctive types of similarity. First, given that the alignment score accounts for pairwise similarity by counting matched positions, and penalizing mismatches with substitution scores and gap costs, a longer sequence would generate a higher score inherently from the more numerous positions to be examined in the matching. This type of similarity derived from alignment score might be provisorily qualified as a “bits” similarity (and the corresponding “bits” dissimilarity, headings of columns 2 and 3, Table 2), in somewhat the same way that a “bit” score was defined from alignment score [3, 20]. Every sequence as single query largely establishes an inherent “reference frame” for computing the alignment scores with subject sequences, a reference frame within which alignment scores can be directly compared and the similarity or dissimilarity is completely well-defined. The “bits” qualification only becomes necessary and significant when comparing results from different query sequences, in reference frames with different baselines and scales. Therefore, a second “regularized” similarity is to be called upon for suitably reconciling and standardizing different reference frames from different query sequences, a similarity measure with which the sequence pair seq.az/a would appropriately score higher than seq.b/1, for instance. Consistent with the notion of “bits” similarity, the self-matching alignment score also shows ostensible length dependency (rows 5–7, Table 2): seq.1 is more self-similar than either seq.b or seq.a because there are more residues in the sequence and consequently more positions, or “bits,” to contribute to the alignment score. This length dependency motivated the formulation of a “base” E value Evalb, in the form of the geometric mean of self-matching alignment scores of participating sequence pair subject and query (Expr M.5), to be applied as a “regularization” of E value Eval to Êval (Expr M.6) ideally suited for comparison across different queries. [Note 1: Similarity and dissimilarity measures derived from Êval are referred to as “regularized” similarity or dissimilarity hence forth, to be understood as a regular or ordinary similarity/dissimilarity measure.] Êval values are shown in column 5, and in column 6 the inverse, i.e. the corresponding similarity measure Ŝ (Expr M.8). Note that the “regularized” similarity Ŝ for seq.az/a is now higher than that for seq.b/1 as desired. Since the alignment score S() is always smaller than S() or S() for any subject s and query q due to mismatches and/or gaps in their respective amino acid sequences and , Eval() would be larger than Evalb(), and from Expr M.6 and thus, Notably, in contrast to Eval’s, and are both 1.602 (column 5, Table 2), each pair being a single threonine-to-glutamine substitution (Table 1(a)). For the three self-matching pairs in rows 5–7, Table 2, the subject sequence is the query sequence; therefore, , and from Expr M.5, and from Expr M.6, whereas self-matching “bits” dissimilarity Eval() is generally greater than 0.0, as shown in Table 2, column 5 versus column 3, rows 5–7. By virtue of R.2, Êval is a proper distance function that by definition must be null for any sequence to itself, hence named “distance E value” in subsection D in Methods. Since the query and subject sequences are of different length in general, Eval() ≠ Eval () (Expr M.2), and thus Êval() ≠ Êval(). Following Brenner et al. [14], the smaller of the two Eval values is assigned to Eval2 for the subject/query pair (Expr M.4), and similarly for Êval2 (Expr M.7). The difference between the two asymmetric Êval’s is generally small in magnitude [Note 2: The difference between Êval() and Êval() is the difference between the logarithms of the subject and query sequence lengths according to Expr M.7, M.6, and M.2. In Fig. 1a, the differences are no larger than 1.1%. The upper bound for values calculated from protein domains in SCOP database is about 1.3%, with an average of about 0.16%.]; for example, seq.b/1 and seq.az/1, rows 2,3, column 5 in Table 2, and others in symbols in green in Fig. 1a. “Regularization” of E value for dissimilarity measure. (a) Eval and Evalb (scale on the left), and Êval and Êval (scale on the right) for pairs of sequences in Table 1(a). The four curves are (from the top): E value (in light green), base E value (purple), distance E value (blue), and E value difference (green), also identified by color-coded labels on Y-axis. Êval is the absolute value of Êval()Êval() displayed in 20-fold. Eval() is larger than Eval() [in light green, first curve from top, and also shown as merge heights in (b)], and Êval() is smaller than Êval() [in blue, third curve from top, and also in (c)]. Since Êval does not alter the order of the first three points of the EvalÊval curve (in blue, numerical data in Table 2), the partial curve from these points are monotonically increasing for the minimum space (seq.{1,b,z}) ⊕ Eval. The break of monotonicity of the EvalÊval curve, notably at the seq.az/a pair, signifies a potential false negative of the “bits” dissimilarity measure Eval. (b) Clustering of the sequences in Table 1(a) on Eval. Note that Eval() > Eval(). (c) Clustering on Êval. Here Êval() = Êval(). Given the small variations of Êval’s from one set of λ,K parameters to another (Table 2, column 5), the clustering dendrogram remains essentially invariant with little change in the ordering of merging heights (cf. Note 4). Both Eval2 and Êval2 are symmetrical, from M.4, M.7, Êval2’s (and Ŝ2’s) are shown in bold in Table 2. Note relationships R.1 and R.2 also hold for Êval2: The relationships for Eval2, Evalb, and Êval2 among various subject/query pairs in Table 2 are shown in Fig. 1a. The comparisons of the clustering dendrograms for Eval2 and Êval2 are shown in Fig. 1b and c, respectively, summarizing numerical results in Table 2. Lastly, it can be readily verified that for rows 4, 8, 9, Table 2, triangular inequality, Expr M.10, holds for “regularized” dissimilarity Êval, but not “bits” dissimilarity Eval: To summarize, the alignment score of 407.0 is a proper “bits” similarity measure of the seq.az/a pair. It is not an underestimate per se, but ostensibly becomes one only as a substitute similarity measure for comparing results from multiple queries when no distinction is made between “bits” similarity and “regularized” similarity. Due to the inflated dissimilarity Eval relative to Êval, the seq.az/a pair would be mistakenly missed, and thus a potential false negative (PFN), in a near neighbor search. As shown in Table 2, “regularized” dissimilarity measure Êval readily recovers false negatives (column 5 versus column 3) that could potentially impact the outcome of operations such as the construction of protein families [15, 16]. Among the family of Êval functions parameterized in substitution matrix and gap scores (and corresponding λ and K, M.7, M.6, M.2), important characteristics on PFN’s and the triangle inequality relations are preserved (noted and shown as examples in Table 2). Case study #2, first 40 domains in SCOP The first 40 domains in SCOP are fetched from the database (version 2.08, updated on 6 January 2023) with Biopython package Bio.SCOP, class and method Scop.getDomains()[0:40]. In Table 3(a), for six of the domains in the protein structure database [Note 3: Protein domains from SCOP database (Table 3) are denoted as dom.d, where d = 1,2, …, and their amino acid sequences are denoted as seq.d as a short hand. Formally dom.d are protein structure domains with 3D conformation data, and seq.d are their amino acid sequences entered into the calculation of alignment scores and E values as query or subject.], their sequences belong in three groups each of degeneracy of 2: seq.1 and 2, seq.3 and 4, and seq.18 and 20. The “bits” similarity and dissimilarity of sequences within a group show length dependency among different groups (Table 3(b), columns 2 and 3), same as the self-matching values in Case study #1 (Table 2, rows 5–7). In particular, the values for the pair seq.1/2 mirror those for the self-matching of seq.1 (row 5, Table 2). Here, dom.1 and 2 are two distinctive 3D protein structure domains from separate X-ray diffraction experiments but share the same amino acid sequence, seq.1seq.2, in contrast to the self-matching of a single sequence seq.1 of domain dom.1 in Table 2; by the same token, Êval2() is a distance of 0 between two domains coincidentally of identical sequences, whereas Êval2() is the self-distance of seq.1 which would be 0 by necessity. If the notion of “bits” similarity were to be extended to “bits” identity, then seq.18/20 would be “more identical” (in the “bits” sense) than seq.3/4 or seq.1/2, whereas the “regularized” identity (arising from “regularized” dissimilarity and similarity) would be universal for all domain groups with degenerate sequences (columns 4, 5, Table 3(b)). For identity as a limiting case and a form of exact similarity, the “regularization” perhaps would prove to be more consequential than a mere semantics exercise. Table 3Amino acid sequences of degenerate pairs and their similarity and dissimilarity scores.(a)Domain id, dAmino acid sequence, 𝕕Notes 1 slfeqlggqaavqavtaqfyaniqadatvatffngidmpnqtnktaaflc aalggpnawtgrnlkevhanmgvsnaqfttvighlrsaltgagvaaalve qtvavaetvrgdvvtv SCOP domain d1dlwa_ (length 116 residues) 2 slfeqlggqaavqavtaqfyaniqadatvatffngidmpnqtnktaaflc aalggpnawtgrnlkevhanmgvsnaqfttvighlrsaltgagvaaalve qtvavaetvrgdvvtv SCOP domain d1uvya_ (length 116 residues) 3 slfaklggreaveaavdkfynkivadptvstyfsntdmkvqrskqfafla yalggasewkgkdmrtahkdlvphlsdvhfqavarhlsdtltelgvpped itdamavvastrtevlnmpqq SCOP domain d1dlya_ (length 121 residues) 4 slfaklggreaveaavdkfynkivadptvstyfsntdmkvqrskqfafla yalggasewkgkdmrtahkdlvphlsdvhfqavarhlsdtltelgvpped itdamavvastrtevlnmpqq SCOP domain d1uvxa_ (length 121 residues) 18 gllsrlrkrepisiydkiggheaievvvedfyvrvladdqlsaffsgtnm srlkgkqveffaaalggpepytgapmkqvhqgrgitmhhfslvaghlada ltaagvpsetiteilgviaplavdvtsgesttapv SCOP domain d1s56b_ (length 135 residues) 20 gllsrlrkrepisiydkiggheaievvvedfyvrvladdqlsaffsgtnm srlkgkqveffaaalggpepytgapmkqvhqgrgitmhhfslvaghlada ltaagvpsetiteilgviaplavdvtsgesttapv SCOP domain d1s61b_ (length 135 residues)(b)s/q (subject, query)S(𝕤, 𝕢) (“bits” similarity)Eval(𝕤, 𝕢) (“bits” dissimilarity)Êval(𝕤, 𝕢) (“regularized” dissim.)Ŝ(𝕤, 𝕢) (“regularized” sim.) 1 /2 580.02.645e-590.01 3 /4 616.01.846e-630.01 18 /20 680.07.809e-710.01(a) Among the first 40 domains fetched from SCOP database (Biopython interface package Bio.SCOP, class and method Scop.getDomains()[0:40]) for Case study #2, three domain pairs (domain names shown in bold italics in the Notes column) are doubly-degenerate, sharing pairwise identical sequences: dom.{1,2}, dom.{3,4}, and dom.{18,20}.(b) Similarity and dissimilarity scores. Amino acid sequences of degenerate pairs and their similarity and dissimilarity scores. (a) Among the first 40 domains fetched from SCOP database (Biopython interface package Bio.SCOP, class and method Scop.getDomains()[0:40]) for Case study #2, three domain pairs (domain names shown in bold italics in the Notes column) are doubly-degenerate, sharing pairwise identical sequences: dom.{1,2}, dom.{3,4}, and dom.{18,20}. (b) Similarity and dissimilarity scores. Figure 2 shows the clustering of the set of 40 domains according to either Eval2 or Êval2 as the dissimilarity measure. In Fig. 2b, degenerate sequence groups other than the three doubly-degenerate groups in Table 3 are readily recognizable by the merge height of 0 [Note 4: Merge heights are dissimilarity levels at which leaves and branches merge in a clustering tree, numerically marked on the Y-axis of dendrogram plots in Figs 1–3)]: one group of degeneracy of 3, three groups of degeneracy of 4, and one group of degeneracy of 8. Clustering of 40 domains (dom.0 through dom.39) in Case study #2: (a) clustering on Eval. (b) Clustering on Êval. Three groups are of degeneracy of 2: dom.{1,2} and dom.{3,4}, in branch E and C, respectively, and dom.{18,20} in branch B. One group of degeneracy of 3: dom.{34,35,39} in branch B. Groups of degeneracy of 4: dom.{11,12,17,19} in branch D, and two others in branch B. One group of degeneracy of 8: dom.{22,25,27,28,29,30,31,32} in branch B. Clustering of 180 domains (dom.0' through dom.179') in Case study #3: (a) clustering on Eval. A threshold at 1e-50 produces the same 11 clusters in the SCOP subset file at the same E value threshold of 1e-50 in the ASTRAL compendium. (b) Clustering on Êval. The threshold of 55.0020 generates 11 clusters, the same number of clusters as in (a). In addition to the identification of sequence-degenerate groups, the Eval-Êval relationship (viz. a plot similar to that colored in blue in Fig. 1a) shows that 87.7% of the sequence pairs of the set of 40 SCOP domains are potential false negatives. And, for Eval’s, of 83.5% of the triplets the triangle inequality is violated. Case study #3, first 180 domains of the ASTRAL domain subset @E value of 1e-50 in SCOP The ASTRAL compendium of the SCOP database provides protein structure domain subsets according to E value thresholds ranging from 1.0e-50 to 1.0e+1 [14]. [Note 5: Rather than protein structure domains, the unit of classification of the database, it is possible, and indeed readily justifiable, to cluster sequences instead into representative subsets if called for by the subject of interest.] From the subset file astral-scopedom-seqres-sel-gs-e100m-verbose-e-50-2.08.txt, at the lowest threshold E value of 1.0e-50, the Stable domain identifiers (sid) of the first 180 domains are extracted and the sequences fetched with Astral.getSeq(Scop.getDomainBySid(sid)) individually. Figure 3 shows the clustering of domain sequences according to Eval2 in Fig. 3a or Êval2 in Fig. 3b. At the E value threshold of 1.0e-50, the 11 groups in Fig. 3a correctly reconstruct the same clusters in the ASTRAL subset file. In Fig. 3b, re-clustering with Êval2 shows that the 10 clusters in the branch colored orange are now reduced to 5; of the 5 reductions, 3 are due to the removal of degeneracies of 2 and 3 of the groups seq.{0',2'} (sid d3nira_d1ejga_) and seq.{1',8',9'} (sid d5d8va_d3a38a_d3a39a_), respectively, and the remaining 2 reductions due to the lowering of merge heights for the group seq.{5',3',4'} (sid d2dsxa_d5nw3a_d1yk4a_) relative to other groups. The reductions would allow six groups, instead of only one presently, to be selected from the branches colored in green. In other words, the 11 clusters in Fig. 3b for Êval2 are more diverse than those in Fig. 3a for Eval2 with sequence degeneracy and double- and triple-representations. Similar to Case study #2, the rates of PFN’s and triangle inequality violations are high, at 97.5% and 92.4%, respectively. Beyond the first 180 domains above, in the ASTRAL compendium file astral-scopedom-seqres-sel-gs-e100m-verbose-e-50-2.08.txt, there are a total of 302 566 of domains factored into 58 375 clusters at the threshold Eval of 1.0e-50, of which 44 440 clusters are singletons (e.g. seq.{0'..9'} in Fig. 3). Of these, 23 515 are non-degenerate clusters each of a unique sequence, with the remaining 20 925 in 4759 groups of degeneracy of up to 175 (e.g. groups seq.{1',8',9'} and seq.{0',2'} in Fig. 3). Re-clustering with Êval2 would have at least deselected 16 166 domains with degenerate, redundant sequences (20 925–4759), in favor of other domains and clusters of non-redundant sequences to be drawn from the 13 935 complex, non-singleton clusters, significantly improving the sequence diversity within the entire subset. Case study #4, distance function and metrication of protein sequence space Of the four axiomatic properties of a metric space (Methods, subsection G), positivity M.13, and symmetry M.15, are satisfied by both dissimilarity measures Eval2 and Êval2: Significantly, the reflexivity property, M.14, for self-distance of 0.0, is satisfied by “regularized” dissimilarity Êval2 only: whereas self-matching dissimilarity Eval2 is greater than 0: M.4 and M.2 with , and illustrated in Table 2, rows 5–7. The remaining axiomatic property of metric space, triangle inequality, M.16, holds for the “regularized” dissimilarity Êval2 as demonstrated for sequences in Case study #1, in Table 2, rows 8 and 9. Formally, the relationship M.10 is rearranged algebraically to M.12 in which contributions from sequence lengths and alignment scores are refactored into two separate, bracketed terms. Rather than a formal proof of the deconstructed relationship M.12, either analytically or by enumeration and complete induction, Eval2, Êval2, and the two bracketed terms in the expression are calculated from triplets of structure domains randomly taken from the SCOP database for analysis. [Note 6: For some structure domains in SCOP database, amino acid residues are given non-standard one-letter codes, such as x, b, or z, if they are undetermined (x) or ambiguous (b or z) in X-ray diffraction experiments. Also, letter X marks interruptions and discontinuities in the amino acid sequence of a structure domain. Although these non-standard amino acid letter codes are in the alphabet of substitution matrix for the calculation of alignment score (Align class of Bio.Align subpackage), sequences containing non-standard amino acids are outside the set of normal, naturally occurring protein sequences (Methods, subsection G). These atypical structure domains are therefore by-passed in the random sampling of SCOP domains for data points in Fig. 4.] While Eval2 fails the condition of triangle inequality, i.e. the left-hand side of R.4, generalized to any sequence triplets, falls below y = 0 in Fig. 4a, Êval2 values on the other hand largely satisfy the condition of triangle inequality, i.e. the left-hand side of generalized R.4a is greater than 0 and falls to the right of x = 0. Of the two bracketed terms in M.12 for Êval2, the residual sequence length dependency term makes a smaller contribution than the second term of alignment scores (Fig. 4b). As shown in red in the inset, for the small number of cases (4.7%) where the triangle inequality fails: (i) the violation is minimal, i.e. the left-hand side of M.12 has a small negative value, only marginally less than zero, and (ii) the alignment scores sum to 0 (the second bracketed term in M.12), with a relatively small, non-zero value for the sequence length term (the first bracketed term in M.12), which is traceable to two specific circumstances of the sequence lengths: either t ≠ u ≠ v, or u = v. These observations suggest that the interplay between sequence length and alignment score in the distance function Êval2 (M.2, M.6, M.7) and in the evaluation of M.12 may play a significant role in the minimal violation of triangle inequality shown in Fig. 4b. Its origin notwithstanding, and however minor it may be, the violation nonetheless implies a lesser metric space (e.g. M.17 and M.18, but not M.16), for which Êval2 is the distance function. To determine the weaker triangle inequality for the lesser metric space, consider first the data points to the right of the dividing line in Fig. 4b with the relationship Distributions of numerical values for the metric property of triangle inequality. (a) Comparison of the left-hand side of M.10 for Eval2 and Êval2, demonstrating triangle inequality in general does not hold for the former. (b) Relationship of the two bracketed terms in Expr M.12, with the inset showing a close-up view of the area near the origin. The line, extending from the origin through the point (1,-1), is a dividing line that marks the separation of the area to its left, x + y < 0, from the area to its right, x + y > 0 where the triangle inequality holds. There are only a relatively small number of cases (4.7%) in which triangle inequality is violated minimally (along the Y-axis and shown in red in inset). NB. For the space (SCOP) ⊕ Eval, the triangle inequality is violated in nearly all cases (99.1%), with predominantly high K″ values as large as e+55. which is equivalent to where K′ = 1. Secondly, for data points to the left of the dividing line, where δ > 0, which, upon rearrangement, becomes where K″() = 1 + δ/(Êval2() + Êval2()) > 1, and K″ > K′. Let Kappa = max(K″()) for all triplets {t,u,v}, then effectively combining both R.5 and R.6 above, for all data points in Fig. 4b, a relationship specified exactly for Kappa-relaxed triangle inequality M.17. K″ is readily calculated from data in Fig. 4b, with a maximum of at least 1.0017 for domains d1lcnb_d1uiaa_, and d4phia_ among random triplets. Therefore, instead of triangle inequality M.16, Êval2 satisfies a minimally relaxed triangle inequality M.17 with Kappa of about 1.0017 [Note 7: The value of Kappa is subject to an exhaustive enumeration of all triplets of SCOP domain sequences. However, from a close examination of the sequences of the domains d1lcnb_d1uiaa_, and d4phia_ and other triplets in Fig. 4b violating the triangle inequality, specific sequence patterns were observed and the length dependency can be used for extrapolating the value of Kappa to a limit of 1.0436 (1.0398 for open_gap_score of −13.00), a theoretical upper bound for any set of polypeptide sequences. It would be interesting also to further trace the source of the small but evidently not insignificant deviation in the non-unitary Kappa, e.g. the length n in M.2, or various parameters in the calculation of alignment score S, factors that might strengthen the lesser metric space of a weakened triangle inequality M.17 to M.16, restoring Kappa back to 1.], thus encoding a semi metric space for protein sequences in the SCOP database. The distribution of positives and negatives of the sum of the two bracketed terms of M.12, viz. those above or below the dividing line in Fig. 4b, remains invariant for different parameter values; for example, for open_gap_score of −13.0 (λ and K of 0.292 and 0.071, respectively), Kappa is 1.0014. It is worth noting that for the small and trivial set of first three sequences in Table 1(a), the triangle inequality holds for the minimum space (seq.{1,b,z}) ⊕ Eval without the need for the “regularized” distance function Êval. Whether or not there may exist additional sequences that could expand the small space, it is reasonable to conjecture that most if not all sets of protein sequences of bioinformatic interests would be more similar to those from SCOP domain sequences than seq.{1,b,z}, for which triangle inequality be violated and database-wide operations susceptible to potential false negatives without regularized E value function Êval. Also worth noting is that the space (SCOP) ⊕ Eval cannot be accommodated by any relaxed triangle inequality relationship M.17 of a reasonable value of Kappa due to the dominant and massive violations noted in Fig. 4b. With the “regularized” dissimilarity as the distance function, the metricity of protein sequence space may benefit from certain efficient search operations [17, 21] to be exploited by similarity and other searches such as multiple sequence alignment for example [22]. In a recent study [19], a new E value for BLAST searches has been introduced with improved significance estimates (as well as certain computational and operational efficiencies). The new procedure improves the statistical significance as the primary goal, absent of any algebraic transformations similar to M.5, M.6 that are essential in the E value regularization. The query-length induced pattern of alignment score and E values shown respectively in columns 2 and 3 of Table 2 should be readily verifiable for the new E value calculations, to which the regularization procedure described herein would likely be applicable for sequence alignment comparisons over multiple queries. Moreover, the regularized dissimilarity scores based on the statistically improved E value [19] may be investigated particularly with regard to the Kappa value, for either a strict or a relaxed metricity (cf. Note 7). Beyond the simulated E value calculation reported herein, regularizing E value toward a dissimilarity measure and distance function for metricating protein sequence space may be further explored for the following. (i) In contrast to fixed parameter set (as noted in Methods, subsection B), for mixed parameters (e.g. BLOSUM matrices and/or gap scores, theoretically speaking), E value regularization (Table 2) would be expected to be more nuanced, e.g. more complicated variants of expression M.12, in a manner likely dependent on specific mixed parameter sets, which would require closer examinations as necessary in practice. (ii) The relevant procedures in principle may be incorporated into the BLAST+ package (http://blast.ncbi.nlm.nih.gov/Blast.cgi) for example. Also, in the search for new protein families [16], a “sequence landscape” was constructed from the results of “all-against-all” sequence searches from MMseqs2 [23], with the alignment coverage as threshold and E value as dissimilarity criterion. It would be interesting to examine E values in MMseqs2 in the manner outlined in this report. Methods All computations and analyses are carried out in Python (version 3.11), with the Biopython suite for bioinformatics [24], specifically the Align module in the suite for sequence alignment, and the Bio.SCOP subpackage [25] for accessing protein structure data in the hierarchical database SCOP [10, 11], version 2.08 updated on 6 January 2023 [26]. Python libraries SciPy and matplotlib are used for clustering and dendrogram generation and for data plotting, respectively. The system for simulated E value calculations is described in subsection B below. For this study, the relevant functions are defined as follows: A. Alignment score S, from the PairwiseAligner class in the Align package of Biopython, where and are the amino acid sequences of subject s and query q, respectively, with the alignment parameters for the score method: open_gap_score, −11.0, extend_gap_score, −1.0, substitution_matrix, ‘BLOSUM62’, and Align.PairwiseAligner.mode, ‘global’. B. E value, computed as a function of S [2, 5], or bit-score S′ [3, 20], where m and n are respectively the database size and the query length, with m of 108 [14], and S′ the bit-score [3, 20], expressed in terms of alignment score S (from M.1), and statistical parameters λ and K of 0.267 and 0.041 respectively [2, 5–7], specific for the alignment parameters in Expr M.1. Since Eval() ≠ Eval() in general, the smaller of the two is assigned to Eval2 for the subject/query pair s and q [14]: N.B. A computational study in protein sequence comparison study (NCBI blast, MMseqs2) often proceeds, at least at the start, with a fixed set parameters (such as dataset size, amino acid substitution matrix and gap scores and corresponding λ and K listed above), with which a baseline too may be established for the regularization of E value for dissimilarity measure. Of these parameters, the database size m is a multiplicative factor of Eval (M.2, M.2a) and thus has no effect on the order of numerical values in column 3 of Table 2. Effects of alternative sets of remaining parameters are further listed and noted in Table 2. C. Base E value, geometric mean of self-matching E values for subject and query s and q, as a “standardization” factor for Eval. D. Distance E value, Êval and Êval2 E. ‘Regularized’ similarity Ŝ and Ŝ2 following general exponential relationship between similarity and dissimilarity measures [8, 9]. F. Triangle inequality for the sequence triplet {t,u,v} states that: where, without loss of generality, Êval2() is the largest among the three pairwise Êval2’s. Substituting M.7 for Êval2, and then M.6 and M.5 for Êval, and M.2 for Eval, the first term on the left-hand side of M.10, Êval2(), becomes: where and are the sequences of seq.t and seq.v and t and v are their lengths. Substituting the expanded form of Êval2() above (M.11), and similarly for the two remaining terms, M.10 algebraically becomes the following, with the left-hand side being the linear sum of two bracketed terms: In this deconstructed form, contributions from sequence lengths and from alignment scores to the metric property (subsection G) of triangle inequality M.10 are refactored as two individual terms that are analyzed more readily (Results and Discussion). G. Metric space, is a space, denoted as where formally a set is defined together with function d(x,y), or metric, for a distance measure between set members, i.e. protein sequences x and y in , with the following four axiomatic properties for all members x,y [21]: positivity reflexivity (identity of indiscernibles) symmetry triangle inequality A “lesser” metric space is a metric space with some of the axiomatic properties modified to a more relaxed, weakened condition. Specifically, a semi metric space is a space for which triangle inequality M.16 is replaced with a weaker inequality: Kappa-relaxed triangle inequality [27] where Kappa ≥ 1, or quadrilateral inequality [28] These two semi metric spaces are also known as the b-metric and the g-metric space, respectively. H. Systems information. Data processing and computations were carried out on a Linux virtual machine (Debian 12 operating system) hosted in Qubes OS hypervisor (4.2.3) running on a Dell 3505 computer, with dual-core Ryzen 5 processor and 16 megabytes of memory. Key Points The E value of BLAST similarity searches is qualified as “bits” dissimilarity. The E value of BLAST similarity searches is qualified as “bits” dissimilarity. Leveraging the E value framework, we formulate a “regularized” dissimilarity that resolves certain peculiarities in the assessment of sequence similarity (Case study #1). Leveraging the E value framework, we formulate a “regularized” dissimilarity that resolves certain peculiarities in the assessment of sequence similarity (Case study #1). The “regularized” dissimilarity satisfies the important property of zero self-distance for a proper distance function, and transparently addresses identity as a limiting and ultimate form of similarity (Case study #2). The “regularized” dissimilarity satisfies the important property of zero self-distance for a proper distance function, and transparently addresses identity as a limiting and ultimate form of similarity (Case study #2). Validated for triangle inequality, the fourth and final axiomatic property of a metric space (Case study #4), the “regularized” dissimilarity is a proper distance function for metricating protein sequence space. Validated for triangle inequality, the fourth and final axiomatic property of a metric space (Case study #4), the “regularized” dissimilarity is a proper distance function for metricating protein sequence space. Put in practice, the “regularized” dissimilarity improves the sequence diversity of clustering and subset selection and helps identify potential false negatives in near neighbor searches (Case study #3). Put in practice, the “regularized” dissimilarity improves the sequence diversity of clustering and subset selection and helps identify potential false negatives in near neighbor searches (Case study #3). Acknowledgements This is an independent research work, with no academic, governmental, corporate, or institutional funding or sponsorship. The author thanks the reviewers for their comments and critiques which greatly helped improve this report, and Oxford University Press for defraying publication costs. Funding None declared. Data availability Sequence data in the report were publicly available from SCOP database [26], and analysis procedures in Biopython package [24]. Numerical data in Case studies #1 to #4, Figs 1–4, and Tables 1–3 are available upon request. References Associated Data Data Availability Statement Sequence data in the report were publicly available from SCOP database [26], and analysis procedures in Biopython package [24]. Numerical data in Case studies #1 to #4, Figs 1–4, and Tables 1–3 are available upon request.