Title:A Spectral Rotation Method with Triplet Periodicity Property for Planted Motif Finding Problems
Volume: 22
Issue: 10
Author(s): Xun Wang, Shudong Wang and Tao Song*
Affiliation:
- School of Electrical Engineering and Automation, Tiangong University, Tianjin 300387,China
Keywords:
Gene detection, motif finding, visualization method, fast algorithm, fourier spectrums, planted motif finding problem.
Abstract:
Background: Genes are known as functional patterns in the genome and are presumed
to have biological significance. They can indicate binding sites for transcription factors and they
encode certain proteins. Finding genes from biological sequences is a major task in computational
biology for unraveling the mechanisms of gene expression.
Objective: Planted motif finding problems are a class of mathematical models abstracted from the
process of detecting genes from genome, in which a specific gene with a number of mutations is
planted into a randomly generated background sequence, and then gene finding algorithms can be
tested to check if the planted gene can be found in feasible time.
Methods: In this work, a spectral rotation method based on triplet periodicity property is proposed
to solve planted motif finding problems.
Results: The proposed method gives significant tolerance of base mutations in genes. Specifically,
genes having a number of substitutions can be detected from randomly generated background
sequences. Experimental results on genomic data set from Saccharomyces cerevisiae reveal that
genes can be visually distinguished. It is proposed that genes with about 50% mutations can be
detected from randomly generated background sequences.
Conclusion: It is found that with about 5 insertions or deletions, this method fails in finding the
planted genes. For a particular case, if the deletion of bases is located at the beginning of the gene,
that is, bases are not randomly deleted, then the tolerance of the method for base deletion is
increased.
