HISEA: HIerarchical SEed Aligner for PacBio data

Seedability: optimizing alignment parameters for sensitive sequence comparison

Motivation

Most sequence alignment techniques make use of exact k-mer hits, called seeds, as anchors to optimize alignment speed. A large number of bioinformatics tools employing seed-based alignment techniques, such as Minimap2 , use a single value of k per sequencing technology, without a strong guarantee that this is the best possible value. Given the ubiquity of sequence alignment, identifying values of k that lead to more sensitive alignments is thus an important task. To aid this, we present Seedability , a seed-based alignment framework designed for estimating an optimal seed k-mer length (as well as a minimal number of shared seeds) based on a given alignment identity threshold. In particular, we were motivated to make Minimap2 more sensitive in the pairwise alignment of short sequences.

Results

The experimental results herein show improved alignments of short and divergent sequences when using the parameter values determined by Seedability in comparison to the default values of Minimap2 . We also show several cases of pairs of real divergent sequences, where the default parameter values of Minimap2 yield no output alignments, but the values output by Seedability produce plausible alignments.

Availability and implementation

https://github.com/lorrainea/Seedability (distributed under GPL v3.0).

Levenshtein Distance, Sequence Comparison and Biological Database Search

Levenshtein edit distance has played a central role-both past and present-in sequence alignment in particular and biological database similarity search in general. We start our review with a history of dynamic programming algorithms for computing Levenshtein distance and sequence alignments. Following, we describe how those algorithms led to heuristics employed in the most widely used software in bioinformatics, BLAST, a program to search DNA and protein databases for evolutionarily relevant similarities. More recently, the advent of modern genomic sequencing and the volume of data it generates has resulted in a return to the problem of local alignment. We conclude with how the mathematical formulation of Levenshtein distance as a metric made possible additional optimizations to similarity search in biological contexts. These modern optimizations are built around the low metric entropy and fractional dimensionality of biological databases, enabling orders of magnitude acceleration of biological similarity search.

conLSH: Context based Locality Sensitive Hashing for mapping of noisy SMRT reads

Single Molecule Real-Time (SMRT) sequencing is a recent advancement of Next Gen technology developed by Pacific Bio (PacBio). It comes with an explosion of long and noisy reads demanding cutting edge research to get most out of it. To deal with the high error probability of SMRT data, a novel contextual Locality Sensitive Hashing (conLSH) based algorithm is proposed in this article, which can effectively align the noisy SMRT reads to the reference genome. Here, sequences are hashed together based not only on their closeness, but also on similarity of context. The algorithm has O(n^ρ+1) space requirement, where n is the number of sequences in the corpus and ρ is a constant. The indexing time and querying time are bounded by On^ρ+1·lnnln1P₂ and O(n^ρ) respectively, where P₂ > 0, is a probability value. This algorithm is particularly useful for retrieving similar sequences, a widely used task in biology. The proposed conLSH based aligner is compared with rHAT, popularly used for aligning SMRT reads, and is found to comprehensively beat it in speed as well as in memory requirements. In particular, it takes approximately 24.2% less processing time, while saving about 70.3% in peak memory requirement for H.sapiens PacBio dataset.

Tools and Strategies for Long-Read Sequencing and De Novo Assembly of Plant Genomes

The commercial release of third-generation sequencing technologies (TGSTs), giving long and ultra-long sequencing reads, has stimulated the development of new tools for assembling highly contiguous genome sequences with unprecedented accuracy across complex repeat regions. We survey here a wide range of emerging sequencing platforms and analytical tools for de novo assembly, provide background information for each of their steps, and discuss the spectrum of available options. Our decision tree recommends workflows for the generation of a high-quality genome assembly when used in combination with the specific needs and resources of a project.

Comparative genome analysis reveals niche-specific genome expansion in Acinetobacter baumannii strains

The nosocomial pathogen Acinetobacter baumannii acquired clinical significance due to the rapid development of its multi-drug resistant (MDR) phenotype. A. baumannii strains have the ability to colonize several ecological niches including soil, water, and animals, including humans. They also survive under extremely harsh environmental conditions thriving on rare and recalcitrant carbon compounds. However, the molecular basis behind such extreme adaptability of A. baumannii is unknown. We have therefore determined the complete genome sequence of A. baumannii DS002, which was isolated from agricultural soils, and compared it with 78 complete genome sequences of A. baumannii strains having complete information on the source of their isolation. Interestingly, the genome of A. baumannii DS002 showed high similarity to the genome of A. baumannii SDF isolated from the body louse. The environmental and clinical strains, which do not share a monophyletic origin, showed the existence of a strain-specific unique gene pool that supports niche-specific survival. The strains isolated from infected samples contained a genetic repertoire with a unique gene pool coding for iron acquisition machinery, particularly those required for the biosynthesis of acinetobactin. Interestingly, these strains also contained genes required for biofilm formation. However, such gene sets were either partially or completely missing in the environmental isolates, which instead harbored genes required for alternate carbon catabolism and a TonB-dependent transport system involved in the acquisition of iron via siderophores or xenosiderophores.