Metadata-Version: 2.4
Name: quickmers
Version: 0.1.2
Summary: Fast k-mer distance utilities in C with Python bindings
Author-email: Kian Jalilian <kian2000.jalilian@gmail.com>
Maintainer-email: Nathalie Gocht <nathalie.gocht@b-tu.de>, Kian Jalilian <kian2000.jalilian@gmail.com>
License-Expression: LGPL-3.0-or-later
Project-URL: Homepage, https://github.com/Schlieplab/quickmers
Project-URL: Source, https://github.com/Schlieplab/quickmers
Project-URL: Issues, https://github.com/Schlieplab/quickmers/issues
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: C
Classifier: Operating System :: OS Independent
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: COPYING
License-File: COPYING.LESSER
Requires-Dist: numpy>=1.24
Dynamic: license-file

# QuickMers

[![PyPI Version](https://img.shields.io/pypi/v/quickmers)](https://pypi.org/project/quickmers)
[![License](https://img.shields.io/badge/License-LGPL--3.0--or--later-blue)](LICENSE)


## Overview

**QuickMers** is a high-performance library for computing distances between k-mers (short DNA sequences), implemented in C with Python bindings. It provides fast functions for:

- **Hamming distance** – number of mismatches between equal-length sequences.
- **Levenshtein (edit) distance** – minimum number of insertions, deletions, or substitutions needed to transform one sequence into another.

The library leverages **bitwise operations for Hamming distance** and the **Myers bit-parallel algorithm** for edit distance. On systems with **AVX2 instructions**, computations are further accelerated.


## Installation

**Planned:** Quickmers will be available on [PyPI](https://pypi.org/) in the future.  
Install using pip:
```bash
python -m pip install quickmers
```

or manually:

```bash
python setup.py install
```

## Usage

```python
import numpy as np
from quickmers import (
    hamming_distance_array,
    hamming_distance,
    levenshtein_distance,
    levenshtein_distance_array,
    levenshtein_distance_array_with_min_dist
)
```
### 1. Hamming Distance

#### Signature:
```python
hamming_distance(sequence1: str, sequence2: str) -> int
```

Compute the Hamming distance between two sequences of equal length.

```python
d = hamming_distance("ACGT", "TCGA")
print(d)  # Output: 2
```


### 2. Hamming Distance (array)

#### Signature
```python
hamming_distance_array(query: str, targets: Union[List[str], np.ndarray]) -> np.ndarray
```

Compute Hamming distances between one query sequence and a list of target sequences.

```python
query = "ACGT"
targets_list = ["ACGT", "TCGA", "CGTA"]
targets_array = np.array(targets_list, dtype=object)

distances1 = hamming_distance_array(query, targets_list)
distances2 = hamming_distance_array(query, targets_array)

print(distances1) # Output: array([0, 2, 4])
print(distances2) # Output: array([0, 2, 4])
```


### 3. Levenshtein Distance

#### Signature
```python
levenshtein_distance(sequence1: str, sequence2: str) -> int
```

Compute the edit distance between two sequences.

```python
d = levenshtein_distance("ACGT", "CGTA")
print(d)  # Output: 2
```

### 4. Levenshtein Distance (array)

#### Signature
```python
levenshtein_distance_array(query: str, targets: Union[List[str], np.ndarray]) -> np.ndarray
```

Compute edit distances between a query sequence and a list of sequences.

```python
query = "ACGT"
targets = ["ACGT", "TCGA", "CGTA"]
distances = levenshtein_distance_array(query, targets)
print(distances)  # Output: array([0, 2, 2])
```

### 5. Levenshtein Distance with Minimum Distance

#### Signature
```python
levenshtein_distance_array_with_min_dist(query: str, targets: Union[List[str], np.ndarray], min_distance: int) -> Tuple[bool, List[Optional[int]]]
```
Compute the Levenshtein (edit) distance between a query k-mer and a list of target k-mers, with **early exit** if a minimum distance is violated.  

This function is useful when you want to skip unnecessary calculations once a target is "too close" to the query, which can save significant computation time for long lists.

```python
query = "ACGT"
targets = ["AGGG", "TCGA", "CGTA"]
early_exit, distances = levenshtein_distance_array_with_min_dist(query, targets, 1)
print(early_exit) # Output: False
print(distances)  # Output: array([2, 2, 2])
```

## Implementation Details
- **Hamming distance:** computed using bitwise operations on 64-bit integers for speed. The sequence length has to be 32 or lower.
- **Levenshtein distance:** implemented with **Myers bit-parallel algorithm** for rapid edit distance computation. The sequence length has to be 64 or lower.
- **Array functions:** can take Python lists or NumPy object arrays as input.
- **AVX2 acceleration:** if your CPU supports AVX2, internal loops are vectorized for faster computation.
- **Memory management:** all functions use efficient pre-allocated arrays to minimize Python overhead.

## Performance

Benchmarking was performed on randomly generated k-mers of varying lengths.
Values represent the number of string pairs distances calculated per second.

### Benchmark Results

| Function | k=5 | k=10 | k=15 | k=20 | k=25 | k=30 |
|----------|----------|----------|----------|----------|----------|----------|
| `hamming_distance` | 9,505,940 | 9,192,009 | 8,866,906 | 8,555,942 | 8,249,809 | 7,946,207 |
| `hamming_distance_array` | 49,038,568 | 47,807,278 | 44,236,469 | 38,861,603 | 35,788,375 | 33,238,156 |
| `levenshtein_distance` | 7,499,375 | 6,407,775 | 5,797,060 | 5,131,730 | 4,688,698 | 4,267,584 |
| `levenshtein_distance_array` | 26,354,634 | 20,227,311 | 16,396,735 | 13,399,246 | 11,772,501 | 10,360,021 |

> Results may vary depending on CPU architecture, compiler optimizations, and whether AVX2 instructions are available.


## References

[1] Gene Myers. 1999. *A fast bit-vector algorithm for approximate string matching based on dynamic programming*. J. ACM 46, 3 (May 1999), 395-415. https://doi.org/10.1145/316542.316550

## License

This software is licensed under **LGPL-3.0-or-later**.

Copyright 2025 Alexander Schliep
