Searching for Repeats, As an Example of Using the Generalised Ruzzo-Tompa Algorithm to Find Optimal Subsequences with Gaps

Overview

Journal Int J Bioinform Res Appl

Specialty Biology

Date 2014 Jul 4

PMID 24989859

Citations 1

Authors

John L Spouge

Leonardo Marino-Ramirez

Sergey L Sheetlin

Affiliations

Soon will be listed here.

Abstract

Some biological sequences contain subsequences of unusual composition; e.g. some proteins contain DNA binding domains, transmembrane regions and charged regions, and some DNA sequences contain repeats. The linear-time Ruzzo-Tompa (RT) algorithm finds subsequences of unusual composition, using a sequence of scores as input and the corresponding 'maximal segments' as output. In principle, permitting gaps in the output subsequences could improve sensitivity. Here, the input of the RT algorithm is generalised to a finite, totally ordered, weighted graph, so the algorithm locates paths of maximal weight through increasing but not necessarily adjacent vertices. By permitting the penalised deletion of unfavourable letters, the generalisation therefore includes gaps. The program RepWords, which finds inexact simple repeats in DNA, exemplifies the general concepts by out-performing a similar extant, ad hoc tool. With minimal programming effort, the generalised Ruzzo-Tompa algorithm could improve the performance of many programs for finding biological subsequences of unusual composition.

Citing Articles

Most of the tight positional conservation of transcription factor binding sites near the transcription start site reflects their co-localization within regulatory modules.

Acevedo-Luna N, Marino-Ramirez L, Halbert A, Hansen U, Landsman D, Spouge J BMC Bioinformatics. 2016; 17(1):479.

PMID: 27871221 PMC: 5117513. DOI: 10.1186/s12859-016-1354-5.

References

Frith M . Gentle masking of low-complexity sequences improves homology search. PLoS One. 2011; 6(12):e28819. PMC: 3242753. DOI: 10.1371/journal.pone.0028819. View

Jurka J, Kapitonov V, Pavlicek A, Klonowski P, Kohany O, Walichiewicz J . Repbase Update, a database of eukaryotic repetitive elements. Cytogenet Genome Res. 2005; 110(1-4):462-7. DOI: 10.1159/000084979. View

Feschotte C . Transposable elements and the evolution of regulatory networks. Nat Rev Genet. 2008; 9(5):397-405. PMC: 2596197. DOI: 10.1038/nrg2337. View

Benson G . Tandem repeats finder: a program to analyze DNA sequences. Nucleic Acids Res. 1998; 27(2):573-80. PMC: 148217. DOI: 10.1093/nar/27.2.573. View

Huda A, Marino-Ramirez L, Jordan I . Epigenetic histone modifications of human transposable elements: genome defense versus exaptation. Mob DNA. 2010; 1(1):2. PMC: 2836006. DOI: 10.1186/1759-8753-1-2. View

Marino-Ramirez L, Jordan I . Transposable element derived DNaseI-hypersensitive sites in the human genome. Biol Direct. 2006; 1:20. PMC: 1538576. DOI: 10.1186/1745-6150-1-20. View

Garzon-Martinez G, Zhu Z, Landsman D, Barrero L, Marino-Ramirez L . The Physalis peruviana leaf transcriptome: assembly, annotation and gene model prediction. BMC Genomics. 2012; 13:151. PMC: 3488962. DOI: 10.1186/1471-2164-13-151. View

Marino-Ramirez L, Lewis K, Landsman D, Jordan I . Transposable elements donate lineage-specific regulatory sequences to host genomes. Cytogenet Genome Res. 2005; 110(1-4):333-41. PMC: 1803082. DOI: 10.1159/000084965. View

Lander E, Linton L, Birren B, Nusbaum C, Zody M, Baldwin J . Initial sequencing and analysis of the human genome. Nature. 2001; 409(6822):860-921. DOI: 10.1038/35057062. View

10.

Gribskov M, Robinson N . Use of receiver operating characteristic (ROC) analysis to evaluate sequence matching. Comput Chem. 1996; 20(1):25-33. DOI: 10.1016/s0097-8485(96)80004-0. View

11.

Cornette J, Cease K, Margalit H, Spouge J, Berzofsky J, Delisi C . Hydrophobicity scales and computational techniques for detecting amphipathic structures in proteins. J Mol Biol. 1987; 195(3):659-85. DOI: 10.1016/0022-2836(87)90189-6. View

12.

Altschul S, Gish W, Miller W, Myers E, Lipman D . Basic local alignment search tool. J Mol Biol. 1990; 215(3):403-10. DOI: 10.1016/S0022-2836(05)80360-2. View

13.

Huda A, Tyagi E, Marino-Ramirez L, Bowen N, Jjingo D, Jordan I . Prediction of transposable element derived enhancers using chromatin modification profiles. PLoS One. 2011; 6(11):e27513. PMC: 3210180. DOI: 10.1371/journal.pone.0027513. View

14.

Miller W, Myers E . Sequence comparison with concave weighting functions. Bull Math Biol. 1988; 50(2):97-120. DOI: 10.1007/BF02459948. View

15.

Morgulis A, Gertz E, Schaffer A, Agarwala R . A fast and symmetric DUST implementation to mask low-complexity DNA sequences. J Comput Biol. 2006; 13(5):1028-40. DOI: 10.1089/cmb.2006.13.1028. View

16.

Morgulis A, Gertz E, Schaffer A, Agarwala R . WindowMasker: window-based masker for sequenced genomes. Bioinformatics. 2005; 22(2):134-41. DOI: 10.1093/bioinformatics/bti774. View

17.

Frith M . A new repeat-masking method enables specific detection of homologous sequences. Nucleic Acids Res. 2010; 39(4):e23. PMC: 3045581. DOI: 10.1093/nar/gkq1212. View

18.

Brendel V, Dohlman J, Blaisdell B, Karlin S . Very long charge runs in systemic lupus erythematosus-associated autoantigens. Proc Natl Acad Sci U S A. 1991; 88(4):1536-40. PMC: 51054. DOI: 10.1073/pnas.88.4.1536. View

19.

Simbaqueba J, Sanchez P, Sanchez E, Nunez Zarantes V, Chacon M, Barrero L . Development and characterization of microsatellite markers for the Cape gooseberry Physalis peruviana. PLoS One. 2011; 6(10):e26719. PMC: 3198794. DOI: 10.1371/journal.pone.0026719. View

20.

KYTE J, Doolittle R . A simple method for displaying the hydropathic character of a protein. J Mol Biol. 1982; 157(1):105-32. DOI: 10.1016/0022-2836(82)90515-0. View