Research article · 2013
Conference abstractPublished 5 Sep 2018
An ultra-efficient global alignment algorithm for comparing highly similar sequences
Academia Sinica, Taiwan
Abstract
Select any words in the title or abstract, or press this and choose a sentence.
We present an ultra-efficient global alignment algorithm for comparing similar genomes and for read mapping in Next Generation Sequencing (NGS), which can process long reads as fast as short reads. Furthermore, it can tolerate much higher error rates. Our parallel read mapping algorithm, KART, is 3 to 10 times faster than the well-known Bowtie2 and BWAMEM algorithm. On pairwise alignment of human genome sequences, the extended KART is 260 times faster than current methods. The same idea has also been applied to RNA-seq, producing DART, a quick and accurate mapping algorithm. (1) KART: a divide-and-conquer algorithm for NGS read alignment (2) DART: a fast and accurate RNA-seq mapper with a partitioning strategy: Besides getting high quality alignment efficiently, our algorithm can simultaneously perform variant calling in about the same amount of time. To achieve the abovementioned objectives, we design a divide-and-conquer alignment strategy giving a query sequence P and one reference sequence Q; identifying all locally maximal exact matches as simple region pairs in sequence Q with sequence P and then clustering the simple region pairs (simple pairs) according to their coordinates in the database to form the bases of global alignment and fixing the overlaps between adjacent simple region pairs and then filling gaps between adjacent simple region pairs by inserting normal region pair (normal pairs) to produce a complete alignment. The crux of the algorithm is that simple pairs can be aligned in linear time and all simple pairs and normal pairs can be aligned independently and in parallel. After dividing the query sequence P sufficiently, those pairs that require gapped alignment only have an average length of 21.
Subjects
Biochemistry & BiotechnologyAsk about this article
Answers come only from this article's title, abstract and keywords, each sentence pointing to where it comes from. Your question is sent to OpenAI to write the answer. Scholars Central does not store it.
Similar by topic
Research article · 2013
A new sequence alignment algorithm based on hybrid intelligence algorithm
Letter · 23 Apr 2022
Phylogeny of Different Helicobacter pylori Strains could not be Explained by 16S rRNA Gene due to High Similarity in Gene Sequence Across Strains
Opinion · 31 Dec 2024
Designing Ultra-efficient DC-DC Converters for Low-power Electronics in IoT Devices
Brief report · 30 Sep 2021
A Report on Ultra-Efficient 3D Printed Catalysts
More from this journal
The newest in Journal of Proteomics & Bioinformatics.
Perspective · 30 Dec 2025
Advances in Molecular Docking for Predicting Protein Ligand Interactions
Commentary · 30 Dec 2025
Machine Learning in Bioinformatics Transforming Biological Data into Predictive Insights
Perspective · 30 Dec 2025
Post-Translational Modifications as Dynamic Regulators of Proteome Complexity and Cellular Function
Conferences in this field
Upcoming conferences in this field.
Follow
New articles from what you follow go into your email digest, once you agree to alert emails.
- JournalJournal of Proteomics & Bioinformatics
- SubjectBiochemistry & Biotechnology
- BylineArticles whose byline prints “Wen-Lian Hsu”

