Repository: cogent3/cogent3 (python)

Issue:
dotplot doesn't use argument for kmer size, defualt k is buggy
`_SequenceCollectionBase.dotplot()`does not pass on the argument for kmer size to the resulting `Dotplot`. This is a simple fix. `Dotplot` has a `k` argument that should receive on the k from `_SequenceCollectionBase.dotplot()` 

As `Dotplot` does not propagate any user-defined k, it will always use `cogent3.align.pycompare._calc_seed_size()` to calculate the k size, and the logic in this function is dubious. 


```python3
def _calc_seed_size(w: int, t: int) -> int:
    """computes k-mer size

    Parameters
    ----------
    w : int
        window size
    t : int
        threshold for minimum number of matches

    Returns
    -------
    int
        returns the larger of (w // k) * k <= t OR w - t + 1
    """
    assert 0 < t <= w, f"threshold={t} > window size={w}"

    # k should be such that (w % k) * k < threshold
    denom = w - t + 1
    return max(min(w // denom, t), denom)
```

`    # k should be such that (w % k) * k < threshold` This is not maintained!! 

In fact, the smaller the proportion of `t/w`, the larger the returned `k` is!!

```python3
  _calc_seed_size(20, 15)
  # 6
```

```python3
  _calc_seed_size(20, 10)
  # 11
```

```python3
  _calc_seed_size(20, 5)
  # 16
```

In the latter cases, `k` is larger than the threshold! 










Pull request:
bug fixes for dotplot and related code, fixes #1619
fixes #1619

Patch:
diff --git a/src/cogent3/align/pycompare.py b/src/cogent3/align/pycompare.py
index ac68fe348..2cdf0216e 100644
--- a/src/cogent3/align/pycompare.py
+++ b/src/cogent3/align/pycompare.py
@@ -488,7 +488,7 @@ class MatchedSeqPaths:
         return trace
 
 
-def _calc_seed_size(w: int, t: int) -> int:
+def _calc_seed_size(w: int, t: int, min_val: int = 5) -> int:
     """computes k-mer size
 
     Parameters
@@ -497,17 +497,23 @@ def _calc_seed_size(w: int, t: int) -> int:
         window size
     t : int
         threshold for minimum number of matches
+    min_val : int
+        minimum k-mer size
 
     Returns
     -------
     int
-        returns the larger of (w // k) * k <= t OR w - t + 1
+        k-mer size
     """
-    assert 0 < t <= w, f"threshold={t} > window size={w}"
 
-    # k should be such that (w % k) * k < threshold
-    denom = w - t + 1
-    return max(min(w // denom, t), denom)
+    assert 0 < t <= w, f"threshold={t} > window size={w}"
+    d = w - t
+    if w == t:
+        return w
+    elif d > t:
+        return t
+    k = t // d
+    return max(k, min_val)
 
 
 def find_matched_paths(
@@ -530,7 +536,8 @@ def find_matched_paths(
     window : int
         size of sequence segment to be compared
     threshold : int
-        Minimum number of positions that must be equal within the window.Less than or equal to window.
+        Minimum number of positions that must be equal within the window.
+        Less than or equal to window.
 
     Returns
     -------
@@ -572,4 +579,16 @@ def find_matched_paths(
 
         paths.append(ref_coord, other_coord)
 
+    for y_intercept in paths.paths:
+        if len(paths.paths[y_intercept]) == 1:
+            continue
+        merged = [paths.paths[y_intercept][0]]
+        for x2, y2 in paths.paths[y_intercept][1:]:
+            x1, y1 = merged[-1]
+            if x1.overlap(x2):
+                merged[-1] = (x1 | x2, y1 | y2)
+            else:
+                merged.append((x2, y2))
+        paths.paths[y_intercept] = merged
+
     return paths
diff --git a/src/cogent3/core/alignment.py b/src/cogent3/core/alignment.py
index 624bb89a3..9d8539fd9 100644
--- a/src/cogent3/core/alignment.py
+++ b/src/cogent3/core/alignment.py
@@ -1859,6 +1859,7 @@ class _SequenceCollectionBase:
             isinstance(self, AlignmentI),
             window=window,
             threshold=threshold,
+            k=k,
             min_gap=min_gap,
             xtitle=None if annotated else seq1.name,
             ytitle=None if annotated else seq2.name,


Test patch:
diff --git a/tests/test_align/test_compare.py b/tests/test_align/test_compare.py
index 9e2213fb8..f45dbb631 100644
--- a/tests/test_align/test_compare.py
+++ b/tests/test_align/test_compare.py
@@ -60,14 +60,15 @@ def test_find_matched_k_eq_1():
 
 
 def test_calc_seed_size():
-    x = _calc_seed_size(20, 20)
-    assert x == 20
+    """default seed size should not be larger than than threshold"""
+    for i in range(2, 30):
+        x = _calc_seed_size(30, i)
+        assert x <= i
 
-    x = _calc_seed_size(20, 19)
-    assert x == 10
 
-    x = _calc_seed_size(20, 14)
-    assert x == 7
+def test_calc_seed_size_singleton_window():
+    x = _calc_seed_size(1, 1)
+    assert x == 1
 
 
 def test_segment():
@@ -389,6 +390,16 @@ def test_find_matched_with_rc():
     assert x == yrc
 
 
+def test_find_matched_with_small_seed():
+    s1 = make_seq("CACACCACTGCAGTCGGATAGACC", moltype="dna", name="s1")
+    s2 = make_seq("GGTCTATCCGACTGCAGTGGTGTG", moltype="dna", name="s2")
+    k = 2
+    expect = _brute_force(s1, s2, 4, 4)
+    sk = SeqKmers(s1, k=k, canonical="ACGT")
+    got = find_matched_paths(seq_kmers=sk, seq1=s1, seq2=s2, window=4, threshold=4)
+    assert got.paths == expect.paths
+
+
 @pytest.mark.parametrize("w,t", [(4, 4), (3, 3)])
 def test_find_matched_1seq(w, t):
     s = make_seq("CACACCACTGCAGTCGGATAGACC", moltype="dna", name="s1")