Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Adjusting a Traverse01:12

Adjusting a Traverse

59
In the site survey of a four-sided traverse, internal angles are essential to ensure geometric accuracy. The survey revealed that the sum of the measured internal angles was 359 degrees and 48 minutes, which is 12 minutes less than the expected 360 degrees. This discrepancy signals an error likely arising from measurement inaccuracies during the fieldwork.To rectify this error, the adjustment process involved distributing the 12-minute shortfall equally across the four internal angles. By...
59
Survival Tree01:19

Survival Tree

86
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
 Building a Survival Tree
Constructing a...
86
RACE - Rapid Amplification of cDNA Ends02:35

RACE - Rapid Amplification of cDNA Ends

6.4K
Rapid Amplification of cDNA Ends, or RACE, is one of the most effective methods to obtain a full-length cDNA from an mRNA sequence between a known internal region to the unknown sequence at the 5’ or 3’ end. The unknown region is cloned in the cDNA by a gene-specific primer that binds the known end, and a hybrid primer that attaches a predefined anchor sequence to the unknown end of the cDNA. The sequence in between is amplified by PCR with an anchor primer and a gene-specific...
6.4K
Evolutionary Relationships through Genome Comparisons02:54

Evolutionary Relationships through Genome Comparisons

5.7K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
5.7K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Barbell reveals and resolves demultiplexing and trimming issues in Nanopore data.

Bioinformatics (Oxford, England)·2026
Same author

mim: A lightweight auxiliary index to enable fast, parallel, gzipped FASTQ parsing.

bioRxiv : the preprint server for biology·2025
Same author

A near-tight lower bound on the density of forward sampling schemes.

Bioinformatics (Oxford, England)·2024
Same author

A near-tight lower bound on the density of forward sampling schemes.

bioRxiv : the preprint server for biology·2024
Same author

Aligning distant sequences to graphs using long seed sketches.

Genome research·2023

Related Experiment Video

Updated: Jul 5, 2025

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
08:57

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin

Published on: August 14, 2018

15.9K

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

Ragnar Groot Koerkamp1, Pesho Ivanov1

  • 1Department of Computer Science, ETH Zurich, Rämistrasse 101, Zurich 8092, Switzerland.

Bioinformatics (Oxford, England)
|January 24, 2024
PubMed
Summary
This summary is machine-generated.

A new A*PA aligner offers faster exact pairwise sequence alignment using an A* shortest path algorithm. It achieves significant speedups, especially for long DNA sequences with high divergence, improving computational biology research.

More Related Videos

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.4K
Operation of the Collaborative Composite Manufacturing CCM System
10:09

Operation of the Collaborative Composite Manufacturing CCM System

Published on: October 1, 2019

6.6K

Related Experiment Videos

Last Updated: Jul 5, 2025

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
08:57

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin

Published on: August 14, 2018

15.9K
A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

35.4K
Operation of the Collaborative Composite Manufacturing CCM System
10:09

Operation of the Collaborative Composite Manufacturing CCM System

Published on: October 1, 2019

6.6K

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genomics

Background:

  • Sequence alignment is fundamental to computational biology.
  • Existing exact alignment algorithms struggle with long sequences and high divergence.

Purpose of the Study:

  • To develop a practical algorithm for exact pairwise sequence alignment in linear-like time.
  • To improve the efficiency of aligning long and divergent sequences.

Main Methods:

  • Utilized the A* shortest path algorithm for exact global pairwise alignment.
  • Extended seed heuristics with match chaining, gap costs, and inexact matches.
  • Integrated match pruning and diagonal transition for enhanced A* search.

Main Results:

  • A*PA demonstrates near-linear runtime scaling (n^1.06 to n^1.24) for sequences up to 107 bp.
  • Achieved >500x speedup over Edlib and BiWFA for 107 bp sequences at 4% divergence.
  • Showed 3x median speedup on long ONT reads (human samples) with <10% divergence.
  • Performed 1.7x faster than Edlib and BiWFA for sequences from different human samples.

Conclusions:

  • The A*PA aligner provides a significant advancement in exact pairwise sequence alignment efficiency.
  • The algorithm's performance is robust across various sequence lengths and divergence levels.
  • A*PA is a valuable tool for analyzing large genomic datasets, particularly long reads and divergent sequences.