BOL: Related items

odgi: optimized dynamic genome/graph implementation

Abhimanyu Singh — Tue, 01 Feb 2022 23:42:21 -0600

odgi provides an efficient and succinct dynamic DNA sequence graph model, as well as a host of algorithms that allow the use of such graphs in bioinformatic analyses.

Careful encoding of graph entities allows odgi to efficiently compute and transform pangenomes with minimal overheads. odgi implements a dynamic data structure that leveraged multi-core CPUs and can be updated on the fly.

The edges and path steps are recorded as deltas between the current node id and the target node id, where the node id corresponds to the rank in the global array of nodes. Graphs built from biological data sets tend to have local partial order and, when sorted, the deltas be small. This allows them to be compressed with a variable length integer representation, resulting in a small in-memory footprint at the cost of packing and unpacking.

The RAM and computational savings are substantial. In partially ordered regions of the graph, most deltas will require only a single byte.

Address of the bookmark: https://github.com/pangenome/odgi

FOGSAA: Fast Optimal Global Sequence Alignment Algorithm

Jit — Fri, 08 Dec 2017 14:41:08 -0600

Sequence alignment algorithms are widely used to infer similarirty and the point of differences between pair of sequences. FOGSAA is a fast Global alignment algorithm. It is basically a branch and bound approach which starts branch expansion in a greedy way taking the symbols from the given pair of sequences (protein or nucleotide) and results in an optimal alignment faster than conventional dymanic programming techniques. It is also better than the heuristic methods with respect to alignment quality.

Address of the bookmark: http://www.isical.ac.in/~bioinfo_miu/FOGSAA.htm

PPanGGOLiN: Depicting microbial species diversity via a Partitioned PanGenome Graph Of Linked Neighbors

LEGE — Thu, 01 Feb 2024 00:24:32 -0600

PPanGGOLiN (Gautreau et al. 2020) is a software suite used to create and manipulate prokaryotic pangenomes from a set of either genomic DNA sequences or provided genome annotations. It is designed to scale up to tens of thousands of genomes. It has the specificity to partition the pangenome using a statistical approach rather than using fixed thresholds which gives it the ability to work with low-quality data such as Metagenomic Assembled Genomes (MAGs) or Single-cell Amplified Genomes (SAGs) thus taking advantage of large scale environmental studies and letting users study the pangenome of uncultivable species.

A complete documentation is available here.

Address of the bookmark: https://github.com/labgem/PPanGGOLiN

pggb: the pangenome graph builder

biogeek — Sun, 13 Sep 2020 20:54:20 -0500

This pangenome graph construction pipeline renders a collection of sequences into a pangenome graph (in the variation graph model). Its goal is to build a graph that is locally directed and acyclic while preserving large-scale variation. Maintaining local linearity is important for the interpretation, visualization, and reuse of pangenome variation graphs.

Address of the bookmark: https://github.com/pangenome/pggb

The wavefront alignment (WFA) algorithm

BioStar — Sun, 28 Jun 2020 10:17:50 -0500

The wavefront alignment (WFA) algorithm is 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(s^2) memory. Moreover, the WFA 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.

Address of the bookmark: https://github.com/smarco/WFA

JumboDB: tool for de Bruijn graph construction

BioStar — Tue, 17 Aug 2021 13:33:46 -0500

jumboDB tool for fast de Bruijn graph construction from long sequences (reads or genomes) with very low error rate. JumboDB is not a genome assembler by itself but rather a subroutine that translates a set of reads into compressed de Bruijn graph.

More at https://github.com/AntonBankevich/jumboDB

Address of the bookmark: https://github.com/AntonBankevich/jumboDB

VG: variation graph data structures, interchange formats, alignment, genotyping, and variant calling methods

Jit — Tue, 28 Jan 2020 03:53:24 -0600

Variation graphs provide a succinct encoding of the sequences of many genomes. A variation graph (in particular as implemented in vg) is composed of:

nodes, which are labeled by sequences and ids
edges, which connect two nodes via either of their respective ends
paths, describe genomes, sequence alignments, and annotations (such as gene models and transcripts) as walks through nodes connected by edges

Address of the bookmark: https://github.com/vgteam/vg

RNA Bioinformatics and High Throughput Analysis Jena

Sat, 09 Nov 2013 20:03:56 -0600

Research Topics:

High Throughput Sequencing Analysis
Comparative Genomics
Identification and Annotation of Non-coding RNAs
Bioinformatic Analysis and System Biology of Viruses
Coevolution of Proteins and RNAs
Algorithmic Bioinformatics
Phylogenetic Analysis

http://www.rna.uni-jena.de/index.php

ReMILO: reference assisted misassembly detection algorithm using short and long reads.

Jit — Fri, 06 Jul 2018 04:27:49 -0500

ReMILO, a reference assisted misassembly detection algorithm that uses both short reads and PacBio SMRT long reads. ReMILO aligns the initial short reads to both the contigs and reference genome, and then constructs a novel data structure called red-black multipositional de Bruijn graph to detect misassemblies. In addition, ReMILO also aligns the contigs to long reads and find their differences from the long reads to detect more misassemblies.

Address of the bookmark: https://github.com/songc001/remilo

FLAS: fast and high throughput algorithm for PacBio long read self-correction.

Jit — Sat, 22 Jun 2019 12:16:39 -0500

FLAS, a wrapper algorithm of MECAT, to achieve high throughput long read self-correction while keeping MECAT's fast speed. FLAS finds additional alignments from MECAT prealigned long reads to improve the correction throughput, and removes misalignments for accuracy.

Address of the bookmark: https://github.com/baoe/flas