Introduction

wavefront_local is a library implement the wavefront alignment in the local alignment scope. Current implementation like WFA2-lib only support semi-global alignment. wavefront_local fill the gap to the local alignment.

Scoring system

The difficulty of applying WFA to the local alignment is that the WFA scoring system does not award matches. Thus, the best possible score is zero. However, in the local alignment scope, this can be easily achieved by aligning nothing at all. Eizenga and Paten show that the WFA scoring system with mismatch penalty $x$, gap opening penalty $o$, and gap extension penalty $e$, can be related to the classical scoring system with match score $l_c$, mismatch penalty $x_c$, gap opening penalty $o_c$, and gap extension penalty $e_c$ by

\begin{aligned}
&x = 2l_c + 2x_c \\
&o = 2o_c \\
&e = 2e_c + l_c
\end{aligned}

By the identiy

2L + 2X + E = M + N

with $L$ the total matches, $X$ the total mismatches, $E$ the total gap size, $M$ and $N$ the size of text and qury, respectively, Eizenga and Paten prove that the classical score $s_c$ and the WFA score $s_w$ are related by

2s_c + s_w = l_c(M + N)

We extend their observation by penalize the unaligned region in the local scope. In detail, let $J$ be the total size of unaligned region. Then there is the identity

2L + 2X + E + J = M + N

for the local scope. We penalty each step in the unaligned region by $j$. Observe that if set the local-scope WFA scoring system by

\begin{aligned}
&x = 2l_c + 2x_c \\
&o = 2o_c \\
&e = 2e_c + l_c \\
&j = l_c
\end{aligned}

then we recover the relation between the global-scope WFA scoring system and the classical one as

2s_c + s_w = l_c(M + N)

Recurrence of wavefront components in the local alignment scope

The recurrence of wavefront components for the wavefront alignment in the local scope (lWFA) is

\begin{aligned}
&\mathcal{I}_{s,d} = \max(\mathcal{M}_{s-o-e,d-1} + 1, \mathcal{I}_{s-e,d-1} + 1) \\
&\mathcal{D}_{s,d} = \max(\mathcal{M}_{s-o-e,d+1} + 1, \mathcal{D}_{s-e,d+1} +1) \\
&\mathcal{X} = \max(f, \mathcal{M}_{s-x,d} + 2, \mathcal{I}_{s,d}, \mathcal{D}_{s,d}) \\
&\mathcal{M}_{s,d} = \mathcal{X}_{s,d} + 2\mu(m,n)
\end{aligned}

where $f = s / j$ if $0 = s\pmod j$, otherwise $f = -\infty$. Compared with the global WFA, lWFA computes $\mathcal{X}_{s,d}$ by including the possibility that $\mathcal{X}_{s,d}$ corresponds to the start cell of the aligned region. This is achieved by the term $f$. If $0 = s\pmod j$, then the unaligned region of size $f = s / j$ has the score exactly equal to $s$. Otherwise, just set $f = -\infty$.

It can be prove that this recurrence format keeps the $O(sN)$ time complexity and the $O(s^2)$ space complexity. Furthermore, the bidirectional technique also works for the WFA in the local scope, which improve the space complexity from $O(s^2)$ to $O(s)$ while keep the $O(sN)$ time complexity.

pybind11 python langauage binding

Install the pypi package.

$ pip install wavefront_local

There are four functions.

  • wavefront_local._core.cpplwfa
  • wavefront_local._core.cpplbiwfa
  • wavefront_local.pylwfa
  • wavefront_local.pylbiwfa

All functions have the same signature, see the example. To run the example,

$ examples/example.py
  • cpplwfa implements the wavefront alignment in the local scope.
  • cpplbiwfa implements the bidirectional wavefront alignment in the local scope. It use the least time and space (even faster than cpplwfa).
  • pylwfa and pylbiwfa are python prototypes. These have higher readability than the c++ library. One may learn how lWFA and lBiWFA work by reading these python prototypes.

c++ library

To use the c++ library, you need to clone the repository or download a release tarball.

$ git clone https://github.com/ljw20180420/wavefront_local.git
$ cd wavefront_local

Local wavefront alignment (lWFA)

See this example. To compile and run the example,

$ examples/lwfa.sh

Local bidirectional wavefront alignment (lBiWFA)

See this example. To compile and run the example,

$ examples/lbiwfa.sh

Citation

In preparation.

TODO

- skip calculation for $s<e,o+e,x$
- optimize out intialization of fs
- SeqAn3 introduces highly optimized, native low-bit alphabets like seqan3::dna4 (which uses only 2 bits per base to represent A, C, G, T) and seqan3::dna5
- SeqAn3 handles dynamic programming matrices by utilizing specialized allocation stripes and structures that recycle memory buffers.
- compact custom alphabets (bit vector)

- [ ] Skip useless jumping at diagonals which have been passed by previous low-score waves. This prevent redundant extension, thereby the time complexity no longer depends on x.
  - Prove the correctness of skipping useless jumping as follows.
    - The optimal score keep.
    - The iteration get Fr (wavefront).
    - The optimal score is achieved at Fr.
    - The iteration skipping useless jumping achieves optimal score.
- [ ] Implement the technique in the paper: Improving the time and space complexity of the WFA algorithm and generalizing its scoring.
- [ ] find sota library for efficient implementaion
  - [ ] bit vector for recording alignment
  - [ ] efficient sparse matrix
- [ ] manual simd
- [ ] webassembly

Key dates

PyPI data
Data sourced directly from PyPI's database.
  • Released:
Latest release

1 maintainer

PyPI data
Data sourced directly from PyPI's database.
Avatar for ljw20180420 from gravatar.com ljw20180420

Credits

Author: ljw

Requires

Python >=3.14

Report project as malware

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

wavefront_local-0.1.4.tar.gz (17.7 kB view details)

Uploaded Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

wavefront_local-0.1.4-cp314-cp314t-musllinux_1_2_x86_64.whl (1.1 MB view details)

Uploaded CPython 3.14tmusllinux: musl 1.2+ x86-64

wavefront_local-0.1.4-cp314-cp314t-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl (109.8 kB view details)

Uploaded CPython 3.14tmanylinux: glibc 2.24+ x86-64manylinux: glibc 2.28+ x86-64

wavefront_local-0.1.4-cp314-cp314-musllinux_1_2_x86_64.whl (1.1 MB view details)

Uploaded CPython 3.14musllinux: musl 1.2+ x86-64

wavefront_local-0.1.4-cp314-cp314-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl (108.2 kB view details)

Uploaded CPython 3.14manylinux: glibc 2.24+ x86-64manylinux: glibc 2.28+ x86-64

File details

Details for the file wavefront_local-0.1.4.tar.gz.

File metadata

  • Download URL: wavefront_local-0.1.4.tar.gz
  • Upload date:
  • Size: 17.7 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for wavefront_local-0.1.4.tar.gz
Algorithm Hash digest
SHA256 490d90e169948822c19b67f9ece1c1bfc6c7013f4f7f706bacf25f15b70c02ea
MD5 2c1d88fe2d2a03307ee526002d5aa661
BLAKE2b-256 af01c788c1d77008a17c15d9691f76568bb6d9b434505d99e1b1e873084e127c

See more details on using hashes here.

Provenance

The following attestation bundles were made for wavefront_local-0.1.4.tar.gz:

Publisher: release.yml on ljw20180420/wavefront_local

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file wavefront_local-0.1.4-cp314-cp314t-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for wavefront_local-0.1.4-cp314-cp314t-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 cc7aa5d6ef33be15c2a364e609269695090d633a116ea78250b5d3a92eec05a5
MD5 b94e05d451cff9fe6ecb2c5ccbde712f
BLAKE2b-256 90937ff0604b46d2c1d1d5401387521725a6f217759a66802bb6f9319c67a93d

See more details on using hashes here.

Provenance

The following attestation bundles were made for wavefront_local-0.1.4-cp314-cp314t-musllinux_1_2_x86_64.whl:

Publisher: release.yml on ljw20180420/wavefront_local

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file wavefront_local-0.1.4-cp314-cp314t-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for wavefront_local-0.1.4-cp314-cp314t-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 6cf7b247ce525ef8ab0905415583cc5a700d3e5f040747bf3adaf865020ab9f7
MD5 724f9b15f3565ee361614a701c63f0ea
BLAKE2b-256 6b6dd7bdf0e8b7c4ef4be389c5149226a83444385e32ade7de54cab3235568ec

See more details on using hashes here.

Provenance

The following attestation bundles were made for wavefront_local-0.1.4-cp314-cp314t-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl:

Publisher: release.yml on ljw20180420/wavefront_local

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file wavefront_local-0.1.4-cp314-cp314-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for wavefront_local-0.1.4-cp314-cp314-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 bf2c888668459d3a9103417474d0eafe6203705f43cfe46d6f3a4d7552c29df4
MD5 5ec9c51c83f9f0a346a8477772b3755d
BLAKE2b-256 95b15115976d46245f1b0b8d90f999e8de49827c73d6120bb1d551c1fcfc51c0

See more details on using hashes here.

Provenance

The following attestation bundles were made for wavefront_local-0.1.4-cp314-cp314-musllinux_1_2_x86_64.whl:

Publisher: release.yml on ljw20180420/wavefront_local

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file wavefront_local-0.1.4-cp314-cp314-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for wavefront_local-0.1.4-cp314-cp314-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 430a1a6207a4865459ac226c0a96de1f1e03280fd89bd0833068c3e0a97e6331
MD5 8a7ab8b6e972877cba38c14cd955330c
BLAKE2b-256 b895809773e18fa99bbe3afdd783068c5851f98a9aa93e74e2100fe38614c90e

See more details on using hashes here.

Provenance

The following attestation bundles were made for wavefront_local-0.1.4-cp314-cp314-manylinux_2_24_x86_64.manylinux_2_28_x86_64.whl:

Publisher: release.yml on ljw20180420/wavefront_local

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

Release history Release notifications | RSS feed

This release

0.1.4 This release

5 files

0.1.3

5 files

0.1.2

5 files

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page