Exact global alignment using A* with chaining seed heuristic and match pruning

MOTIVATION

Sequence alignment has been at the core of computational biology for half a century. Still, it is an open problem to design a practical algorithm for exact alignment of a pair of related sequences in linear-like time.

RESULTS

We solve exact global pairwise alignment with respect to edit distance by using the A* shortest path algorithm. In order to efficiently align long sequences with high divergence, we extend the recently proposed seed heuristic with match chaining, gap costs, and inexact matches. We additionally integrate the novel match pruning technique and diagonal transition to improve the A* search. We prove the correctness of our algorithm, implement it in the A*PA aligner, and justify our extensions intuitively and empirically.

On random sequences of divergence d=4% and length n, the empirical runtime of A*PA scales near-linearly with length (best fit n1.06, n≤107 bp). A similar scaling remains up to d=12% (best fit n1.24, n≤107 bp). For n=107 bp and d=4%, A*PA reaches >500× speedup compared to the leading exact aligners Edlib and BiWFA. The performance of A*PA is highly influenced by long gaps. On long (n>500kb) ONT reads of a human sample it efficiently aligns sequences with d<10%, leading to 3× median speedup compared to Edlib and BiWFA. When the sequences come from different human samples, A*PA performs 1.7× faster than Edlib and BiWFA.

AVAILABILITY AND IMPLEMENTATION

github.com/RagnarGrootKoerkamp/astar-pairwise-aligner.

Structure-Function Relationship of Highly Reactive CuOx Clusters on Co3 O4 for Selective Formaldehyde Sensing at Low Temperatures

Designing reactive surface clusters at the nanoscale on metal-oxide supports enables selective molecular interactions in low-temperature catalysis and chemical sensing. Yet, finding effective material combinations and identifying the reactive site remains challenging and an obstacle for rational catalyst/sensor design. Here, the low-temperature oxidation of formaldehyde with CuOx clusters on Co3 O4 nanoparticles is demonstrated yielding an excellent sensor for this critical air pollutant. When fabricated by flame-aerosol technology, such CuOx clusters are finely dispersed, while some Cu ions are incorporated into the Co3 O4 lattice enhancing thermal stability. Importantly, infrared spectroscopy of adsorbed CO, near edge X-ray absorption fine structure spectroscopy and temperature-programmed reduction in H2 identified Cu+ and Cu2+ species in these clusters as active sites. Remarkably, the Cu+ surface concentration correlated with the apparent activation energy of formaldehyde oxidation (Spearman's coefficient ρ = 0.89) and sensor response (0.96), rendering it a performance descriptor. At optimal composition, such sensors detected even the lowest formaldehyde levels of 3 parts-per-billion (ppb) at 75°C, superior to state-of-the-art sensors. Also, selectivity to other aldehydes, ketones, alcohols, and inorganic compounds, robustness to humidity and stable performance over 4 weeks are achieved, rendering such sensors promising as gas detectors in health monitoring, air and food quality control.