WITCH-NG: efficient and accurate alignment of datasets with sequence length heterogeneity
1Department of Computer Science, University of Illinois Urbana-Champaign, Champaign, IL 61820, USA.
Bioinformatics Advances
|March 27, 2023
Summary
We developed WITCH-NG, a faster method for multiple sequence alignment of heterogeneous datasets. It uses Smith-Waterman for improved speed while maintaining accuracy in bioinformatics pipelines.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Multiple sequence alignment is crucial for bioinformatics tasks like phylogeny and structure prediction.
- Sequence datasets often have length heterogeneity due to evolutionary changes or incomplete assembly.
- Existing methods like UPP and WITCH address this but can be computationally intensive.
Purpose of the Study:
- To significantly accelerate the WITCH algorithm for multiple sequence alignment.
- To maintain the high accuracy of WITCH when aligning heterogeneous sequence data.
- To introduce WITCH-NG as a next-generation solution for efficient sequence alignment.
Main Methods:
- Replaced a heuristic search step in WITCH with a polynomial time exact algorithm.
- Implemented the Smith-Waterman algorithm for the critical alignment step.
- Developed the WITCH-NG (Next Generation WITCH) method.
Main Results:
- WITCH-NG achieves comparable accuracy to WITCH in aligning heterogeneous sequences.
- WITCH-NG demonstrates substantial speed improvements over the original WITCH method.
- The new method enhances the efficiency of bioinformatics pipelines.
Conclusions:
- WITCH-NG offers a faster and accurate solution for multiple sequence alignment with length heterogeneity.
- The integration of Smith-Waterman significantly optimizes the alignment process.
- This advancement benefits various bioinformatics applications requiring robust sequence alignment.
Related Concept Videos
03:21RNA-seq
10.2K
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
10.2K
02:54Evolutionary Relationships through Genome Comparisons
5.9K
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.9K