Global, highly specific and fast filtering of alignment seeds
Matthis Ebel1,2, Giovanna Migliorelli1,2, Mario Stanke3,4
1Institute for Mathematics and Computer Science, University of Greifswald, Walther-Rathenau-Str. 47, 17489, Greifswald, Germany.
BMC Bioinformatics
|June 10, 2022
Summary
Geometric hashing significantly reduces false positives in homology search seed finding, a critical step for genome alignment. This method enhances accuracy and efficiency in biological sequence analysis.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Seed finding is a critical initial step for homology search and genome alignment methods.
- It anchors potential alignments to specific sequence position pairs, crucial for limiting computational runtime.
- Spaced seed patterns are commonly used, requiring exact matches at specific positions for local sequence comparison.
Purpose of the Study:
- To introduce a novel method, geometric hashing, for filtering alignment seeds.
- To enhance the specificity and efficiency of homology search algorithms.
Main Methods:
- Geometric hashing combines non-local information from multiple spaced seeds.
- A simple hash function is employed, requiring minimal additional computation time per seed.
- The method was evaluated on human and mouse coding genome sequences.
Main Results:
- Geometric hashing drastically reduced false positives (by approximately a million-fold) compared to standard spaced seed sets.
- High sensitivity was maintained during the filtering process.
- The method demonstrated effectiveness in identifying homologous positions in coding genome regions.
Conclusions:
- Incorporating geometric hashing as a filtering step can improve the runtime and accuracy of homology search and alignment programs.
- This approach offers a significant advancement for various sequence alignment tasks.
- The method shows promise for enhancing large-scale genomic analyses.
Related Concept Videos
03:21RNA-seq
10.4K
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.4K
02:51Multi-species Conserved Sequences
4.3K
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.3K
02:54Evolutionary Relationships through Genome Comparisons
6.2K
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...
6.2K
02:05Gene Evolution - Fast or Slow?
7.5K
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
7.5K