C implementation of the Landau-Vishkin algorithm

Related tags

Algorithms lv89
Overview

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.

Issues
  • Differences between Ukkonen and Landau-Vishkin

    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.
    opened by RagnarGrootKoerkamp 3
  • Code question

    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?

    opened by RagnarGrootKoerkamp 3
  • Other implementations of Landau-Vishkin

    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!

    opened by RagnarGrootKoerkamp 1
Owner
Heng Li
Heng Li
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.

Farhan Izzaturrahman Andiejanto 1 Nov 10, 2021
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

Schrodinger ZHU Yifan 2 Nov 2, 2021
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.

Shepard 5 May 16, 2022
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

Jonas STIRNEMANN 2 Mar 23, 2022
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

Artem Kolpakov 1 Jan 24, 2022
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.

Emir Öztürk 4 Sep 30, 2021
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:

Niklas Mäckle 2 Sep 24, 2021
C Program showing line drawing using DDA algorithm.

Draw-Line-Using-DDA-algorithm C Program showing line drawing using DDA algorithm. How it works ? ??

CodAffection 2 Sep 28, 2021
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.

Lakshan Sandanayaka 2 Sep 21, 2021
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

null 2 Nov 18, 2021
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.

null 1 Nov 13, 2021
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,

Hanlin || Herlin 1 Dec 1, 2021
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

David 2 Mar 26, 2022
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

Guilherme Serafim Kollet 1 Oct 24, 2021
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

octav adrian 4 Nov 5, 2021
Pottery - A container and algorithm template library in C

Pottery - A container and algorithm template library in C

Nicholas Fraser 97 Jul 28, 2022
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

null 39 Jul 30, 2022
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

Mohammad Nazari 9 Jun 16, 2022
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

Tony Trinh 1 Jan 23, 2022