Fast motif matching revisited: high-order PWMs, SNPs and indels
Janne H Korhonen1,2,3, Kimmo Palin4, Jussi Taipale5
1School of Computer Science, Reykjavík University, Reykjavík, Iceland.
Bioinformatics (Oxford, England)
|December 25, 2016
Summary
We developed fast motif matching algorithms for advanced sequence motif models, including variants like SNPs and indels. These algorithms efficiently identify motif sites in large genomic datasets, outperforming traditional methods.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Position weight matrices (PWMs) are common for sequence motifs, but advanced models like Markov representations are gaining traction.
- Learning motif models is well-researched, yet efficient methods for predicting motif sites in new sequences are lacking.
- Analyzing how sequence variants (SNPs, indels) affect motif sites requires efficient computational tools.
Purpose of the Study:
- To develop fast motif matching algorithms for advanced sequence motif models.
- To adapt existing algorithms for high-order position weight matrices (PWMs) and general q-mer dependencies.
- To incorporate sequence variants and their effects into efficient motif matching workflows.
Main Methods:
- Formalized a framework for high-order PWMs to represent motif models with q-mer dependencies.
- Adapted fast PWM matching algorithms to the high-order PWM framework.
- Integrated handling of sequence variants (SNPs, indels) into motif matching algorithms.
Main Results:
- Developed fast motif matching algorithms that perform well on genome-sized datasets.
- Algorithms are significantly faster than basic sliding window methods for multiple motif searches.
- Successfully incorporated sequence variants into efficient motif matching.
Conclusions:
- The developed algorithms provide efficient solutions for motif site prediction using advanced models.
- The software package MOODS offers practical implementation of these fast motif matching algorithms.
- This work addresses the need for efficient tools in motif site analysis considering sequence variations.
Related Concept Videos
01:05Single Nucleotide Polymorphisms-SNPs
19.2K
A single nucleotide polymorphism or SNP is a single nucleotide variation at a specific genomic position in a large population. It is the most prevalent type of sequence variation found in the human genome. Point mutations that occur in more than 1% of the population qualify as SNPs. These are present once every 1000 nucleotides on an average in the human genome. Replacement of a purine with another purine (A/G) or a pyrimidine with another pyrimidine (C/T) is known as a transition. In contrast,...
19.2K
01:30Point and Frameshift Mutations
1.4K
Point mutations are genetic alterations involving the change of a single nucleotide base pair in DNA. Depending on how the alteration affects protein synthesis, they can lead to various consequences.Point mutations fall into the following types:Silent mutations occur when a nucleotide change does not alter the amino acid sequence due to the redundancy of the genetic code. For instance, changing ACC to ACA still encodes threonine, leaving the protein function unaffected. This occurs because...
1.4K
02:26Comparing Copy Number Variations and SNPs
19.0K
Sequencing of the human genome has opened up several best-kept secrets of the genome. Scientists have identified thousands of genome variations that exist within a population. These variations can be a single nucleotide or a larger chromosomal variation.
Copy number variations or CNVs are the structural variations that cover more than 1kb of DNA sequence. The single nucleotide polymorphism (SNP), on the other hand, is a single nucleotide change or a point mutation that is found in more than 1%...
Copy number variations or CNVs are the structural variations that cover more than 1kb of DNA sequence. The single nucleotide polymorphism (SNP), on the other hand, is a single nucleotide change or a point mutation that is found in more than 1%...
19.0K
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
02:26Conservation of Protein Domains Over Different Proteins
14.9K
Protein domains are small structurally independent units that are part of a single amino acid chain. Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to...
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to...
14.9K
01:09Wilcoxon Signed-Ranks Test for Matched Pairs
554
The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...
554