Fast sequence to graph alignment using the graph wavefront algorithm
Motivation: A pan-genome graph represents a collection of genomes and encodes sequence variations between them. It is a powerful data structure for studying multiple similar genomes. Sequence-to-graph alignment is an essential step for the construction and the analysis of pan-genome graphs. However, existing algorithms incur runtime proportional to the product of sequence length and graph size, making them inefficient for aligning long sequences against large graphs. Results: We propose the graph wavefront alignment algorithm (Gwfa), a new method for aligning a sequence to a sequence graph. Although the worst-case time complexity of Gwfa is the same as the existing algorithms, it is designed to run faster for closely matching sequences, and its runtime in practice often increases only moderately with the edit distance of the optimal alignment. On four real datasets, Gwfa is up to four orders of magnitude faster than other exact sequence-to-graph alignment algorithms. We also propose a graph pruning heuristic on top of Gwfa, which can achieve an additional $\sim$10-fold speedup on large graphs. Availability: Gwfa code is accessible at https://github.com/lh3/gwfa.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Ptychographic reconstruction with wavefront initialization
X-ray ptychography is a cutting edge imaging technique providing ultra-high spatial resolutions. In ptychography, phase retrieval, i.e., the recovery of a complex valued signal from intensity-only measurements, is enable…
RetrievalTempestas ex machina: A review of machine learning methods for wavefront control
As we look to the next generation of adaptive optics systems, now is the time to develop and explore the technologies that will allow us to image rocky Earth-like planets; wavefront control algorithms are not only a cruc…
On Learning the Invisible in Photoacoustic Tomography with Flat Directionally Sensitive Detector
In photoacoustic tomography (PAT) with flat sensor, we routinely encounter two types of limited data. The first is due to using a finite sensor and is especially perceptible if the region of interest is large relative to…
SensitivityDeep Microlocal Reconstruction for Limited-Angle Tomography
We present a deep learning-based algorithm to jointly solve a reconstruction problem and a wavefront set extraction problem in tomographic imaging. The algorithm is based on a recently developed digital wavefront set ext…
TILT: topological interface recovery in limited-angle tomography
A novel reconstruction method is introduced for the severely ill-posed inverse problem of limited-angle tomography. It is well known that, depending on the available measurement, angles specify a subset of the wavefront …