Implement DP in SIFTS.fix_range

[NatureGeorge]

Currently, pdb-profiling(v0.2.6) implements a Brute-Force way of obtaining a fixed alignment range. However, not only does it ignore cases like 1qmb_1 but also too inefficient for large protein. Dynamic Programming should be considered. And the Needleman-Wunsch algorithm is a nice choice.

[NatureGeorge]

• Affine Gap Penalties
• Bounded Dynamic Programming: ignore Mildly Boring Alignments (MBAs)
• Linear Space Alignment

[NatureGeorge]

• LRUCache
• Cython Implementation

[NatureGeorge]

• https://github.com/thompsonb/vecalign

[NatureGeorge]

FOGSAA: Fast Optimal Global Sequence Alignment Algorithm can also be considered.

[NatureGeorge]

Fast gap-affine pairwise alignment using the wavefront algorithm

present the wavefront alignment algorithm (WFA), an exact gap-affine algorithm that takes advantage of homologous regions between the sequences to accelerate the alignment process. As opposed to traditional dynamic programming algorithms that run in quadratic time, the WFA runs in time O(ns), proportional to the read length n and the alignment score s, using O(s2) memory. Furthermore, our algorithm exhibits simple data dependencies that can be easily vectorized, even by the automatic features of modern compilers, for different architectures, without the need to adapt the code. We evaluate the performance of our algorithm, together with other state-of-the-art implementations. As a result, we demonstrate that the WFA runs 20–300× faster than other methods aligning short Illumina-like sequences, and 10–100× faster using long noisy reads like those produced by Oxford Nanopore Technologies.

• https://github.com/smarco/WFA

[NatureGeorge]

This discussion could be closed by #9 , #14