Related Experiment Video
Updated: Jul 12, 2026
10:44
Single Cell Multiplex Reverse Transcription Polymerase Chain Reaction After Patch-clamp
Published on: June 20, 2018
Multiple spaced seeds for homology search
1Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada.
Bioinformatics (Oxford, England)
|September 7, 2007
Summary
Researchers developed a novel polynomial-time algorithm for computing multiple spaced seeds, significantly accelerating homology search. This new method drastically reduces computation time compared to previous exponential algorithms, improving biological sequence analysis.
Area of Science:
- Bioinformatics
- Computational Biology
Background:
- Homology search identifies similarities in biological sequences (DNA, protein).
- Spaced seeds, notably in PatternHunter and PatternHunterII, enhance homology search sensitivity and speed.
- Previous methods for computing optimal multiple spaced seeds were computationally intractable (NP-hard) and slow.
Purpose of the Study:
- To develop an efficient algorithm for computing multiple spaced seeds.
- To overcome the NP-hard limitations of previous heuristic approaches.
Main Methods:
- A novel, simple algorithm is presented.
- The algorithm computes good multiple spaced seeds in polynomial time.
Main Results:
- The new algorithm computes superior multiple spaced seeds significantly faster than existing methods.
- A multiple spaced seed comparable to PatternHunterII's was found in 17 seconds, versus 12 days previously.
- Demonstrates a dramatic improvement in computational efficiency.
Conclusions:
- The developed algorithm provides a practical and efficient solution for multiple spaced seed computation.
- This breakthrough changes the perspective on optimizing multiple spaced seeds for homology search.
Related Concept Videos
02:51Multi-species Conserved Sequences
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 DNA...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
02:54Evolutionary Relationships through Genome Comparisons
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...
02:27Trihybrid Crosses
Trihybrid Crosses
Some of Mendel’s crosses examined three pairs of contrasting characteristics. Such a cross is called a trihybrid cross. A trihybrid cross is a combination of three individual monohybrid crosses. For example, plant height (tall vs. short), seed shape (round vs. wrinkled), and seed color (yellow vs. green).
The F1 generation plants of a trihybrid cross are heterozygous for all three traits and produce eight gametes. Upon self-fertilization, these gametes have an equal chance to...
Some of Mendel’s crosses examined three pairs of contrasting characteristics. Such a cross is called a trihybrid cross. A trihybrid cross is a combination of three individual monohybrid crosses. For example, plant height (tall vs. short), seed shape (round vs. wrinkled), and seed color (yellow vs. green).
The F1 generation plants of a trihybrid cross are heterozygous for all three traits and produce eight gametes. Upon self-fertilization, these gametes have an equal chance to...
01:18Dihybrid Crosses
Overview
02:31Homologous Recombination
The basic reaction of homologous recombination (HR) involves two chromatids that contain DNA sequences sharing a significant stretch of identity. One of these sequences uses a strand from another as a template to synthesize DNA in an enzyme-catalyzed reaction. The final product is a novel amalgamation of the two substrates. To ensure an accurate recombination of sequences, HR is restricted to the S and G2 phases of the cell cycle. At these stages, the DNA has been replicated already and the...
02:31Homologous Recombination
The basic reaction of homologous recombination (HR) involves two chromatids that contain DNA sequences sharing a significant stretch of identity. One of these sequences uses a strand from another as a template to synthesize DNA in an enzyme-catalyzed reaction. The final product is a novel amalgamation of the two substrates. To ensure an accurate recombination of sequences, HR is restricted to the S and G2 phases of the cell cycle. At these stages, the DNA has been replicated already and the...