Related Experiment Video
Updated: Feb 27, 2026
07:49
Creating and Applying a Reference to Facilitate the Discussion and Classification of Proteins in a Diverse Group
Published on: August 16, 2017
7.5K
Reducing Alignment Time Complexity of Ultra-Large Sets of Sequences
Álvaro Rubio-Largo1, Leonardo Vanneschi1, Mauro Castelli1
11 Nova Information Management School-NOVA IMS , Universidade Nova de Lisboa, Lisboa, Portugal .
Summary
This study introduces a novel two-level clustering method for multiple sequence alignment (MSA) of ultra-large datasets. The approach significantly reduces computational time while maintaining alignment accuracy for large biological sequence sets.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Multiple Sequence Alignment (MSA) is computationally intensive, especially for large datasets.
- Existing MSA methods face significant computational overhead with thousands of sequences.
Purpose of the Study:
- To develop an efficient method for multiple sequence alignment of ultra-large sequence sets.
- To reduce the runtime of MSA without compromising alignment accuracy.
Main Methods:
- A two-level clustering approach is proposed.
- Level 1: Clustering based on biological composition (amino acid properties).
- Level 2: Sub-clustering based on sequence similarity, followed by alignment of centroid sequences and gap extrapolation.
Main Results:
- The method demonstrates accurate alignments on datasets up to ~100,000 sequences.
- Achieved significant runtime reduction, up to ~45x faster than Kalign on datasets >10,000 sequences.
Conclusions:
- The proposed two-level clustering method offers an efficient solution for MSA of ultra-large sequence datasets.
- This approach significantly accelerates sequence alignment, making large-scale genomic and proteomic analyses more feasible.
Related Concept Videos
01:05Maxam-Gilbert Sequencing
13.2K
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
13.2K
02:51Multi-species Conserved Sequences
4.9K
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
4.9K
03:00Next-generation Sequencing
99.4K
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
99.4K
03:21RNA-seq
12.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...
12.2K
03:36Genome Annotation and Assembly
21.2K
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
21.2K
01:57Sanger Sequencing
775.9K
DNA sequencing is a fundamental technique that is routinely used in the biological sciences. This method can be applied to a range of questions at different scales - from the sequencing of a cloned DNA fragment or the study of a mutation in a gene up to whole-genome sequencing. However, despite the widespread use of sequencing today, it was not until 1977 that Fredrick Sanger and his collaborators developed the chain-termination method to decode DNA sequences. It relies on the separation of a...
775.9K