SEARCH · PubMed Health

Results for “algorithms”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 397 records · Page 22Linked to original sources

PubMed2006

Implementation of a symplectic multiple-time-step molecular dynamics algorithm, based on the united-residue mesoscopic potential energy function.

A symplectic multiple-time-step (MTS) algorithm has been developed for the united-residue (UNRES) force field. In this algorithm, the slow-varying forces (which contain most of the long-range interactions and are, therefore, expensive to compute) are integrated with a larger time step, termed the basic time step, and the fast-varying forces are integrated with a shorter time step, which is an integral fraction of the basic time step. Based on the split operator formalism, the equations of motion were derived. Separation of the fast- and slow-varying forces leads to stable molecular dynamics with longer time steps. The algorithms were tested with the Ala(10) polypeptide chain and two versions of the UNRES force field: the current one in which the energy components accounting for the energetics of side-chain rotamers (U(rot)) can lead to numerically unstable forces and a modified one in which the the present U(rot) was replaced by a numerically stable expression which, at present, is parametrized only for polyalanine chains. With the modified UNRES potential, stable trajectories were obtained even when extending the basic time step to 15 fs and, with the original UNRES potentials, the basic time step is 1 fs. An adaptive multiple-time-step (A-MTS) algorithm is proposed to handle instabilities in the forces; in this method, the number of substeps in the basic time step varies depending on the change of the magnitude of the acceleration. With this algorithm, the basic time step is 1 fs but the number of substeps and, consequently, the computational cost are reduced with respect to the MTS algorithm. The use of the UNRES mesoscopic energy function and the algorithms derived in this work enables one to increase the simulation time period by several orders of magnitude compared to conventional atomic-resolution molecular dynamics approaches and, consequently, such an approach appears applicable to simulating protein-folding pathways, protein functional dynamics in a real molecular environment, and dynamical molecular recognition processes.

Algorithms↗

PubMed2005

An algorithm for progressive multiple alignment of sequences with insertions.

Dynamic programming algorithms guarantee to find the optimal alignment between two sequences. For more than a few sequences, exact algorithms become computationally impractical, and progressive algorithms iterating pairwise alignments are widely used. These heuristic methods have a serious drawback because pairwise algorithms do not differentiate insertions from deletions and end up penalizing single insertion events multiple times. Such an unrealistically high penalty for insertions typically results in overmatching of sequences and an underestimation of the number of insertion events. We describe a modification of the traditional alignment algorithm that can distinguish insertion from deletion and avoid repeated penalization of insertions and illustrate this method with a pair hidden Markov model that uses an evolutionary scoring function. In comparison with a traditional progressive alignment method, our algorithm infers a greater number of insertion events and creates gaps that are phylogenetically consistent but spatially less concentrated. Our results suggest that some insertion/deletion "hot spots" may actually be artifacts of traditional alignment algorithms.

Algorithms↗

PubMed2002

Evaluation of gene-finding algorithms by a content-balancing accuracy index.

A content-balancing accuracy index, called q(9), to evaluate gene-finding algorithms has been proposed. Here the concept of content-balancing means that the evaluation by this index is independent of the coding and non-coding composition of the sequence being evaluated. Since the coding and non-coding compositions are severely unbalanced in eukaryotic genomes, the performance of gene-finding algorithms is either over- or under-evaluated by the widely used accuracy indices, e.g., the correlation coefficient, due to the lack of content-balancing ability. Using the new accuracy index q(9), seven gene-finding algorithms, FGENES; Gene-Mark.hmm; Genie; Genescan; HMMgene; Morgan and MZEF, were compared and evaluated. It is shown that Genescan is still the best one, but with q(9)= 89%, averaged over the prediction for 195 sequences. In addition to the content-balancing ability, q(9) has the merit of having definition in all possible cases. It is also shown that the traditional specificity s(p) carries important information on the performance of the algorithm being evaluated. The set of sensitivity s(n), specificity s(p) and the accuracy q(9) constitutes a complete kit to evaluate gene-finding algorithms at nucleotide level. In addition, a graphic method to compare and evaluate gene-finding algorithms has been proposed, too. Its major advantage is that the overall performance of algorithms can be grasped quickly in a perceivable form. Additionally, the new accuracy index q(9) may be applied to evaluate the performance of weather forecast, clinical diagnosis, psychological examination and protein secondary structure prediction etc.

Algorithms↗

PubMed1994

Evaluation of algorithms for tomographic reconstruction of chemical concentrations in indoor air.

Numerical studies were performed to evaluate and compare four different algorithms for tomographically reconstructing pollutant concentrations in indoor air measured with an optical remote sensing system. With a remote sensing/computed tomography system, two-dimensional maps of air concentrations can be created for an entire room with good spatial and temporal resolution. The success of such a system for characterizing the flow of contaminants in air, exposure assessment, and leak detection depends on the choice of tomographic reconstruction algorithm. A systematic method was developed to evaluate the performance of four algorithms: ART, ART3, SIRT, and SART. One hundred and twenty test maps were reconstructed by each algorithm under ideal and nonideal sampling conditions, and image quality was evaluated using four criteria. The nonideal sampling conditions included simulation of measurement noise and reduction in the number density of rays. Performance of the algorithms was found to be intimately related to the number of peaks in the test maps. The importance of using multiple measures of image quality was underscored by the fact that for some sampling conditions simulated, performance of the algorithms was judged differently depending on the evaluation criteria. Results indicated that using numerical studies is successful for evaluating such algorithms.

Air Pollutants, Occupational↗

PubMed2004

Accuracy of one- and two-dimensional algorithms with optimal image plane position for the estimation of left ventricular mass: a comparative study using magnetic resonance imaging.

The commonly recommended one-dimensional (ID) and two-dimensional (2D) algorithms for left ventricular (LV) mass calculation are limited by assumptions about ventricular geometry and image plane position. To assess the accuracy of these algorithms after eliminating errors associated with image plane position, LV mass was calculated from high quality cardiovascular magnetic resonance imaging (CMR) data sets using ID (modified cube formula; MCF) and 2D algorithms [area-length (AL) and truncated ellipsoid (TE) methods], and the summation of slices (SS) method as reference technique in 25 patients with LV aneurysms, 15 patients with hypertrophic cardiomyopathy, and 10 healthy subjects. Each algorithm in each group overestimated LV mass compared to SS (p <0.05 and p<0.001). In each patient group, the smallest bias to the reference method was observed for the TE algorithm (p<0.001 vs. MCF and p < 0.05 vs. AL). The LV mass interval encompassing the limits of agreement was 120-220 g for MCF, 100-148 g for AL, and 80-136 g for TE. The interstudy reproducibility of the SS technique for the assessment of LV mass was superior compared to the ID and 2D algorithms. We conclude that despite the use of optimized image plane position ID and 2D algorithms are inaccurate for calculation of LV mass in ventricles with normal and distorted LV geometry. Thus, 3D imaging techniques, such as CMR, should be preferred when assessing LV mass.

Adolescent↗

PubMed2005

Validation of an accelerated 'demons' algorithm for deformable image registration in radiation therapy.

A greyscale-based fully automatic deformable image registration algorithm, originally known as the 'demons' algorithm, was implemented for CT image-guided radiotherapy. We accelerated the algorithm by introducing an 'active force' along with an adaptive force strength adjustment during the iterative process. These improvements led to a 40% speed improvement over the original algorithm and a high tolerance of large organ deformations. We used three methods to evaluate the accuracy of the algorithm. First, we created a set of mathematical transformations for a series of patient's CT images. This provides a 'ground truth' solution for quantitatively validating the deformable image registration algorithm. Second, we used a physically deformable pelvic phantom, which can measure deformed objects under different conditions. The results of these two tests allowed us to quantify the accuracy of the deformable registration. Validation results showed that more than 96% of the voxels were within 2 mm of their intended shifts for a prostate and a head-and-neck patient case. The mean errors and standard deviations were 0.5 mm+/-1.5 mm and 0.2 mm+/-0.6 mm, respectively. Using the deformable pelvis phantom, the result showed a tracking accuracy of better than 1.5 mm for 23 seeds implanted in a phantom prostate that was deformed by inflation of a rectal balloon. Third, physician-drawn contours outlining the tumour volumes and certain anatomical structures in the original CT images were deformed along with the CT images acquired during subsequent treatments or during a different respiratory phase for a lung cancer case. Visual inspection of the positions and shapes of these deformed contours agreed well with human judgment. Together, these results suggest that the accelerated demons algorithm has significant potential for delineating and tracking doses in targets and critical structures during CT-guided radiotherapy.

Algorithms↗

PubMed2006

Optimization algorithms and weighting factors for analysis of dynamic PET studies.

Positron emission tomography (PET) pharmacokinetic analysis involves fitting of measured PET data to a PET pharmacokinetic model. The fitted parameters may, however, suffer from bias or be unrealistic, especially in the case of noisy data. There are many optimization algorithms, each having different characteristics. The purpose of the present study was to evaluate (1) the performance of different optimization algorithms and (2) the effects of using incorrect weighting factors during optimization in terms of both accuracy and reproducibility of fitted PET pharmacokinetic parameters. In this study, the performance of commonly used optimization algorithms (i.e. interior-reflective Newton methods) and a simulated annealing (SA) method was evaluated. This SA algorithm, known as basin hopping, was modified for the present application. In addition, optimization was performed using various weighting factors. Algorithms and effects of using incorrect weighting factors were studied using both simulated and clinical time-activity curves (TACs). Input data, taken from [(15)O]H(2)O, [(11)C]flumazenil and [(11)C](R)-PK11195 studies, were used to simulate time-activity curves at various variance levels (0-15% COV). Clinical evaluation was based on studies with the same three tracers. SA was able to produce accurate results without the need for selecting appropriate starting values for (kinetic) parameters, in contrast to the interior-reflective Newton method. The latter gave biased results unless it was modified to allow for a range of starting values for the different parameters. For patient studies, where large variability is expected, both SA and the extended Newton method provided accurate results. Simulations and clinical assessment showed similar results for the evaluation of different weighting models in that small to intermediate mismatches between data variance and weighting factors did not significantly affect the outcome of the fits. Large errors were observed only when the mismatch between weighting model and data variance was large. It is concluded that selection of specific optimization algorithms and weighting factors can have a large effect on the accuracy and precision of PET pharmacokinetic analysis. Apart from carefully selecting appropriate algorithms and variance models, further improvement in accuracy might be obtained by using noise reducing strategies, such as wavelet filtering, provided that these methods do not introduce significant bias.

Algorithms↗

PubMed2001

A sequence alignment algorithm with an arbitrary gap penalty function.

An algorithm for aligning biological sequences is presented that is an adaptation of the sequence generating function approach used in the statistical mechanics of biopolymers. This algorithm uses recursion relationships developed from a partition function formalism of alignment probabilities. It is implemented within a dynamic programming format that closely resembles the forward algorithm used in hidden Markov models (HMM). The algorithm aligns sequences or structures according to the statistically dominant alignment path and will be referred to as the SDP algorithm. An advantage of this method over previous ones is that it allows more complicated and physically realistic gap penalty functions to be incorporated into the algorithm in a facile manner. The performance of this algorithm in a case study of aligning the heavy and light chain from the variable region of an immunoglobulin is investigated.

Algorithms↗

PubMed2001

A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.

Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components; then, in the second stage, certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an O(nalpha(n)) algorithm, based on a Union-Find structure, to find its connected components, where alpha is the inverse Ackerman function. Since for all practical purposes alpha(n) is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.

Algorithms↗

PubMed2002

A structural EM algorithm for phylogenetic inference.

A central task in the study of molecular evolution is the reconstruction of a phylogenetic tree from sequences of current-day taxa. The most established approach to tree reconstruction is maximum likelihood (ML) analysis. Unfortunately, searching for the maximum likelihood phylogenetic tree is computationally prohibitive for large data sets. In this paper, we describe a new algorithm that uses Structural Expectation Maximization (EM) for learning maximum likelihood phylogenetic trees. This algorithm is similar to the standard EM method for edge-length estimation, except that during iterations of the Structural EM algorithm the topology is improved as well as the edge length. Our algorithm performs iterations of two steps. In the E-step, we use the current tree topology and edge lengths to compute expected sufficient statistics, which summarize the data. In the M-Step, we search for a topology that maximizes the likelihood with respect to these expected sufficient statistics. We show that searching for better topologies inside the M-step can be done efficiently, as opposed to standard methods for topology search. We prove that each iteration of this procedure increases the likelihood of the topology, and thus the procedure must converge. This convergence point, however, can be a suboptimal one. To escape from such "local optima," we further enhance our basic EM procedure by incorporating moves in the flavor of simulated annealing. We evaluate these new algorithms on both synthetic and real sequence data and show that for protein sequences even our basic algorithm finds more plausible trees than existing methods for searching maximum likelihood phylogenies. Furthermore, our algorithms are dramatically faster than such methods, enabling, for the first time, phylogenetic analysis of large protein data sets in the maximum likelihood framework.

Algorithms↗

PubMed2005

The URMS-RMS hybrid algorithm for fast and sensitive local protein structure alignment.

We present an efficient and sensitive hybrid algorithm for local structure alignment of a pair of 3D protein structures. The hybrid algorithm employs both the URMS (unit-vector root mean squared) metric and the RMS metric. Our algorithm searches efficiently the transformation space using a fast screening protocol; initial transformations (rotations) are identified using the URMS algorithm. These rotations are then clustered and an RMS-based dynamic programming algorithm is invoked to find the maximal local similarities for representative rotations of the clusters. Statistical significance of the alignments is estimated using a model that accounts for both the score of the match and the RMS. We tested our algorithm over the SCOP classification of protein domains. Our algorithm performs very well; its main advantages are that (1) it combines the advantages of the RMS and the URMS metrics, (2) it searches extensively the transformation space, (3) it detects complex similarities and structural repeats, and (4) its results are symmetric. The software is available for download at biozon.org/ftp/software/urms/.

Algorithms↗

PubMed2006

A polynomial-time algorithm for de novo protein backbone structure determination from nuclear magnetic resonance data.

We describe an efficient algorithm for protein backbone structure determination from solution Nuclear Magnetic Resonance (NMR) data. A key feature of our algorithm is that it finds the conformation and orientation of secondary structure elements as well as the global fold in polynomial time. This is the first polynomial-time algorithm for de novo high-resolution biomacromolecular structure determination using experimentally recorded data from either NMR spectroscopy or X-ray crystallography. Previous algorithmic formulations of this problem focused on using local distance restraints from NMR (e.g., nuclear Overhauser effect [NOE] restraints) to determine protein structure. This approach has been shown to be NP-hard, essentially due to the local nature of the constraints. In practice, approaches such as molecular dynamics and simulated annealing, which lack both combinatorial precision and guarantees on running time and solution quality, are used routinely for structure determination. We show that residual dipolar coupling (RDC) data, which gives global restraints on the orientation of internuclear bond vectors, can be used in conjunction with very sparse NOE data to obtain a polynomial-time algorithm for structure determination. Furthermore, an implementation of our algorithm has been applied to six different real biological NMR data sets recorded for three proteins. Our algorithm is combinatorially precise, polynomialtime, and uses much less NMR data to produce results that are as good or better than previous approaches in terms of accuracy of the computed structure as well as running time.

Algorithms↗

PubMed2005

Developing a computer algorithm to identify epilepsy cases in managed care organizations.

The goal of this study was to develop an algorithm for detecting epilepsy cases in managed care organizations (MCOs). A data set of potential epilepsy cases was constructed from an MCO's administrative data system for all health plan members continuously enrolled in the MCO for at least 1 year within the study period of July 1, 1996 through June 30, 1998. Epilepsy status was determined using medical record review for a sample of 617 cases. The best algorithm for detecting epilepsy cases was developed by examining combinations of diagnosis, diagnostic procedures, and medication use. The best algorithm derived in the exploratory phase was then applied to a new set of data from the same MCO covering the period of July 1, 1998 through June 30, 2000. A stratified sample based on ethnicity and age was drawn from the preliminary algorithm-identified epilepsy cases and non-cases. Medical record review was completed for 644 cases to determine the accuracy of the algorithm. Data from both phases were combined to permit refinement of logistic regression models and to provide more stable estimates of the parameters. The best model used diagnoses and antiepileptic drugs as predictors and had a positive predictive value of 84% (sensitivity 82%, specificity 94%). The best model correctly classified 90% of the cases. A stable algorithm that can be used to identify epilepsy patients within MCOs was developed. Implications for use of the algorithm in other health care settings are discussed.

Adult↗

PubMed2004

Vancomycin dosing in high flux hemodialysis: a limited-sampling algorithm.

PURPOSE: The feasibility of using a limited-sampling algorithm for administration of vancomycin for treatment of vascular-access-related bacteremia in outpatient high flux hemodialysis was investigated. METHODS: The original vancomycin-dosing algorithm used at our hemodialysis unit required stat orders for serum vancomycin concentrations before each hemodialysis session to determine the dose of vancomycin to be administered posthemodialysis. Vancomycin concentration data obtained using this original algorithm from January through September 2001 were retrospectively analyzed to determine how many vancomycin concentrations measured 5-20 microg/mL and identify potential clinical predictors of vancomycin removal. RESULTS: A total of 409 serum vancomycin concentrations were drawn during the study period. Ninety-seven percent of concentrations drawn were within 5-20 microg/mL. Twenty-eight patients had data evaluable to determine pharmacokinetic parameters. Mean +/- S.D. vancomycin removal was 39% +/- 13%. Body weight and duration of dialysis alone, blood flow rate, and dialysate flow rate were not predictive of vancomycin removal. Based on these data, a revised algorithm with limited vancomycin sampling data was initiated in December 2002. Retrospective analysis of concentrations obtained and achieved by this algorithm demonstrated a 70% reduction in the number of vancomycin concentration determinations, with 93% of these concentrations within 5-20 microg/mL. The estimated annual cost saving to the hemodialysis unit with the revised algorithm was 7552 dollars. CONCLUSION: A vancomycin-dosing algorithm using limited concentration monitoring for hemodialysis patients achieved comparable vancomycin concentrations to those found with more frequent monitoring and resulted in significant cost savings.

Algorithms↗

PubMed1998

Algorithms and software for support of gene identification experiments.

MOTIVATION: Gene annotation is the final goal of gene prediction algorithms. However, these algorithms frequently make mistakes and therefore the use of gene predictions for sequence annotation is hardly possible. As a result, biologists are forced to conduct time-consuming gene identification experiments by designing appropriate PCR primers to test cDNA libraries or applying RT-PCR, exon trapping/amplification, or other techniques. This process frequently amounts to 'guessing' PCR primers on top of unreliable gene predictions and frequently leads to wasting of experimental efforts. RESULTS: The present paper proposes a simple and reliable algorithm for experimental gene identification which bypasses the unreliable gene prediction step. Studies of the performance of the algorithm on a sample of human genes indicate that an experimental protocol based on the algorithm's predictions achieves an accurate gene identification with relatively few PCR primers. Predictions of PCR primers may be used for exon amplification in preliminary mutation analysis during an attempt to identify a gene responsible for a disease. We propose a simple approach to find a short region from a genomic sequence that with high probability overlaps with some exon of the gene. The algorithm is enhanced to find one or more segments that are probably contained in the translated region of the gene and can be used as PCR primers to select appropriate clones in cDNA libraries by selective amplification. The algorithm is further extended to locate a set of PCR primers that uniformly cover all translated regions and can be used for RT-PCR and further sequencing of (unknown) mRNA.

Algorithms↗

PubMed1999

A RAPID algorithm for sequence database comparisons: application to the identification of vector contamination in the EMBL databases.

MOTIVATION: Word-matching algorithms such as BLAST are routinely used for sequence comparison. These algorithms typically use areas of matching words to seed alignments which are then used to assess the degree of sequence similarity. In this paper, we show that by formally separating the word-matching and sequence-alignment process, and using information about word frequencies to generate alignments and similarity scores, we can create a new sequence-comparison algorithm which is both fast and sensitive. The formal split between word searching and alignment allows users to select an appropriate alignment method without affecting the underlying similarity search. The algorithm has been used to develop software for identifying entries in DNA sequence databases which are contaminated with vector sequence. RESULTS: We present three algorithms, RAPID, PHAT and SPLAT, which together allow vector contaminations to be found and assessed extremely rapidly. RAPID is a word search algorithm which uses probabilities to modify the significance attached to different words; PHAT and SPLAT are alignment algorithms. An initial implementation has been shown to be approximately an order of magnitude faster than BLAST. The formal split between word searching and alignment not only offers considerable gains in performance, but also allows alignment generation to be viewed as a user interface problem, allowing the most useful output method to be selected without affecting the underlying similarity search. Receiver Operator Characteristic (ROC) analysis of an artificial test set allows the optimal score threshold for identifying vector contamination to be determined. ROC curves were also used to determine the optimum word size (nine) for finding vector contamination. An analysis of the entire expressed sequence tag (EST) subset of EMBL found a contamination rate of 0.27%. A more detailed analysis of the 50 000 ESTs in est10.dat (an EST subset of EMBL) finds an error rate of 0.86%, principally due to two large-scale projects. AVAILABILITY: A Web page for the software exists at http://bioinf.man.ac.uk/rapid, or it can be downloaded from ftp://ftp.bioinf.man.ac.uk/RAPID CONTACT: crispin@cs.man.ac.uk

Algorithms↗

PubMed2002

Analysis of high density expression microarrays with signed-rank call algorithms.

MOTIVATION: We consider the detection of expressed genes and the comparison of them in different experiments with the high-density oligonucleotide microarrays. The results are summarized as the detection calls and comparison calls, and they should be robust against data outliers over a wide target concentration range. It is also helpful to provide parameters that can be adjusted by the user to balance specificity and sensitivity under various experimental conditions. RESULTS: We present rank-based algorithms for making detection and comparison calls on expression microarrays. The detection call algorithm utilizes the discrimination scores. The comparison call algorithm utilizes intensity differences. Both algorithms are based on Wilcoxon's signed-rank test. Several parameters in the algorithms can be adjusted by the user to alter levels of specificity and sensitivity. The algorithms were developed and analyzed using spiked-in genes arrayed in a Latin square format. In the call process, p-values are calculated to give a confidence level for the pertinent hypotheses. For comparison calls made between two arrays, two primary normalization factors are defined. To overcome the difficulty that constant normalization factors do not fit all probe sets, we perturb these primary normalization factors and make increasing or decreasing calls only if all resulting p-values fall within a defined critical region. Our algorithms also automatically handle scanner saturation.

Algorithms↗

PubMed2026

Singletrack: an algorithm for improving memory consumption and performance of gap-affine sequence alignment.

MOTIVATION: Advances in DNA sequencing have outpaced advances in computation, making sequence alignment a major bottleneck in genome data analyses. Classical dynamic programming (DP) algorithms are particularly memory-intensive, especially when computing gap-affine and dual gap-affine alignments. Existing strategies to reduce memory consumption often sacrifice speed or alignment accuracy. RESULTS: We present Singletrack, an efficient algorithm for backtrace gap-affine and dual gap-affine alignments that requires storing a single DP matrix while preserving optimal alignment results. Compared to classical DP algorithms, Singletrack removes the need to store additional matrices (i.e. 2 for gap-affine and 4 for dual gap-affine), significantly reducing memory consumption and, in turn, reducing pressure on the memory hierarchy and improving overall performance. Most importantly, Singletrack is a general backtrace method compatible with state-of-the-art DP-based algorithms and heuristics, such as the Suzuki-Kasahara (SK) and the Wavefront Alignment (WFA) algorithms. We demonstrate that Singletrack reduces memory consumption for both SK and WFA algorithms, lowering SK usage by 2× and 4× and WFA usage by 3× and 5× for gap-affine and dual gap-affine alignments, respectively. Moreover, replacing KSW2's memory-reduction technique with Singletrack accelerates its SK implementation by up to 1.4× at the cost of doubling memory consumption, while Singletrack increases the performance of the WFA implementation in WFA2-lib by 1.2-2.1×. Compared to the efficient linear-memory BiWFA algorithm, the Singletrack-accelerated version of WFA trades a practical increase in memory usage for up to 5.2× higher performance. AVAILABILITY AND IMPLEMENTATION: The Singletrack implementations presented in this work are available on Zenodo (DOI: 10.5281/zenodo.18770585) and GitHub (https://github.com/LorienLV/singletrack).

Algorithms↗