This repo implements the Landau-Vishkin algorithm to compute the edit distance between two strings. This is a fast method for highly similar strings. The actual implementation follows a simplified WFA formulation rather than the original formulation. It also learns a performance trick from WFA. For a pair of ~5Mb HLA sequences with ~123k edits, the implementation here can find the result in 71 seconds, faster than edlib. Edlib will be faster for more divergent sequences.
C implementation of the Landau-Vishkin algorithm
Overview
You might also like...
Based on the spatial resection theory, the algorithm solves the camera position by solving the homography matrix.
Based on the spatial resection theory, the algorithm solves the camera position by solving the homography matrix.
Final Project for Multicore Processors Course at NYU: Parallel Ray Tracing Algorithm
Multicore_ParallelRayTracing Final Project for Multicore Processors Course at NYU: Parallel Ray Tracing Algorithm Team Member: Hanlin He, Yaowei Zong,
C++ and SFML Project that simulates dijkstra algorithm on a non oriented Graph
Dijkstra-Simulator Table of Contents About The Project Built With Getting Started Prerequisites Roadmap Acknowledgments About The Project This is one
Basic algorithm developed in C++
Sequential Search Algorithm O(n) Algoritmo Comportamento Funcional Se o valor que deseja pesquisar dentro do array de fato existir, então a função ret
haha - huh? another hashing algorithm
haha - huh? another hashing algorithm 📙 haha is a hashing algorithm I've written as an exercise and as something to use for myself. It's decently fas
Pottery - A container and algorithm template library in C
Pottery - A container and algorithm template library in C
Blazing fast ⚡⚡⚡ Secure Hash Algorithm solution for React Native with direct C++ bindings
React Native SHA library ⚡ ⚡ ⚡ React-native-sha is a blazing fast ⚡ solution for performing Secure Hashing Algorithm in React Native. Main reason this
I implement what i learned about banker's algorithm in OS course at my uni.
Banker-s-Algorithm The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation
This program uses genetic algorithm to find the best route possible given the conditions.
Genetic Algorithm Table Of Contents Table Of Contents Installation About Terms The Algorithm Default values for the conditions Example result Installa
Comments
-
Differences between Ukkonen and Landau-Vishkin
You write in the readme that the presentation in Landau-Vishkin'89 is closer to modern one than the one from Ukkonen'85, but after some reading I've actually come to the opposite conclusion, so I'm wondering what I'm missing:
- LV finds all occurences of a pattern in a text, while you do global alignment.
- LV 'only' introduces the suffix-tree speedup for constant time extending, which you don't seem to use.
- The recursion presented in Ukkonen and LV otherwise looks the same to me.
-
Code question
// filter out diagonals that are unlikely to reach a better alignment than the current best. Only applicable to global alignment. This is not an approximation. static inline void wf_prune_global(int32_t tl, int32_t ql, int32_t *st, int32_t *en, const wf_diag_t *b)
Looking at this function, this seems to be the approximation/reduction explained in section 4.2 if the WFA paper. However, your comment 'this is not an approximation' sounds like it preserves optimality of the alignment.
What am I missing?
-
Other implementations of Landau-Vishkin
Hej,
I came across this repo when looking for an implementation of the Landau-Vishkin algorithm. I'd like to compare my own work-in-progress algorithm to it, and since WFA is more general, a dedicated implementation for gap-linear or unit costs would be nice.
Are you aware of any other implementations? Or is the lack of them the reason you started this project? Are you planning to publish a paper based on this code that could be cited at some point?
Thanks!
Knapsack Encryption Algorithm is the first general public key cryptography algorithm.
Knapsack Encryption Algorithm is the first general public key cryptography algorithm. It is developed by Ralph Merkle and Mertin Hellman in 1978. As it is a Public key cryptography, it needs two different keys. One is Public key which is used for Encryption process and the other one is Private key which is used for Decryption process.
A C++ implementation of the graph algorithm of finding all strongly connected components with DFS
SinkSCC A C++ implementation of the graph algorithm of finding all strongly connected components with DFS. Details Each SCC of a graph can be treated
The Implementation of quadtree-based multi-thread tiled pyramid building algorithm.
tile-map-parallel-builder Quadtree-based multi-thread tiled pyramid building algorithm. Core Concept NOTE: The level is different from TMS zoom level.
C implementation of a sudoku solver with backtracking algorithm
SUDOKU SOLVER Sudoku solver using backtracking algorithm Sudoku game To solve a sudoku, you need a sudoku. So i made a basic implmentation of one with
Implementation of Dijkstra's algorithm for finding the shortest paths between nodes in a graph using Priority Queue data structure in C
Implementation of Dijkstra's algorithm for finding the shortest paths between nodes in a graph using Priority Queue data structure in C. File "airport
CComp: A Parallel Compression Algorithm for Compressed Word Search
The goal of CComp is to achieve better compressed search times while achieving the same compression-decompression speed as other parallel compression algorithms. CComp achieves this by splitting both the word dictionaries and the input stream, processing them in parallel.
My attempt at implementing the fast voxel traversal algorithm by Amanatides and Woo using OpenGL
Attempt at implementing the fast voxel traversal algorithm Works on both Linux and Windows. Recommended software: Linux: Visual Studio Code / Windows:
C Program showing line drawing using DDA algorithm.
Draw-Line-Using-DDA-algorithm C Program showing line drawing using DDA algorithm. How it works ? ??
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays.
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
This project implemented the Mean Value Coordinates in 3D algorithm in c++
Mean Value Coordinates in 3D [c++] | Paper link on Sciencedirect | Pdf version link | This project implemented the Mean Value Coordinates in 3D algori