Abstract
A weighted biological sequence is a string in which a set of characters may appear at each position with respective probabilities of occurrence. We attempt to locate all the tandem repeats in a weighted sequence. By introducing the idea of equivalence classes in weighted sequences, we identify the tandem repeats of every possible length using an iterative partitioning technique, and present the O(n 2) time algorithm.
Corresponding author: Qing Guo, College of Computer Science, Zhejiang University, Hangzhou, China. Tel: 0086-571-88939701. Fax: 0086-571-88867185.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apostolico, A., Prepamta, F.P.: Optimal Off-line Detection of Repetitions in a string. Theoretical Computer Science 22, 297–315 (1983)
Christodoulakis, M., Iliopoulos, C.S., Mouchard, L., Perdikuri, K., Tsakalidis, A., Tsichlas, K.: Computation of Repetitions and Regularities on Biological Weighted Sequences. Journal of Computational Biology 13(6), 1214–1231 (2006)
Crochemore, M.: An Optimal Algorithm for Computing the Repetitions in a Word. Information Processing Letter 12(5), 244–250 (1981)
Franêk, F., Smyth, W.F., Tang, Y.: Computing All Repeats Using Suffix Arrays. Journal of Automata, Languages and Combinatorics 8(4), 579–591 (2003)
Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press (1997)
Iliopoulos, C.S., Makris, C., Panagis, Y., Perdikuri, K., Theodoridis, E., Tsakalidis, A.: Efficient Algorithms for Handling Molecular Weighted Sequences. IFIP Theoretical Computer Science 147, 265–278 (2004)
Iliopoulos, C.S., Mouchard, L., Perdikuri, K., Tsakalidis, A.: Computing the Repetitions in a Weighted Sequence. In: Proc. of the 8th Prague Stringology Conference (PSC 2003), pp. 91–98 (2003)
Main, M.G., Lorentz, R.J.: An O(nlngn) Algorithm for Finding All Repetitions in a String. Journal of Algorithms 5, 422–432 (1984)
Manber, U., Myers, G.: Suffix Arrays: A New Method for On-Line String Searches. SIAM Journal on Computing 22(5), 935–948 (1993)
Ohno, S.: Repeats of Base Oligomers as the Primordial Coding Sequences of the Primeval Earth and Their Vestiges in Modern Genes. Journal of Molecular Evolution 20, 313–321 (1984)
Stoye, J., Gusfield, D.: Simple and Flexible Detection of Contiguous Repeats Using a Suffix Tree. In: Farach-Colton, M. (ed.) CPM 1998. LNCS, vol. 1448, pp. 140–152. Springer, Heidelberg (1998)
Zhang, H., Guo, Q., Iliopoulos, C.S.: Loose and Strict Repeats in Weighted Sequences. Protein and Peptide Letters 17(9), 1136–1142 (2010)
The Human Genome Project(HGP), http://www.nbgri.nih.gov/HGP/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, H., Guo, Q., Iliopoulos, C.S. (2012). Locating Tandem Repeats in Weighted Biological Sequences. In: Huang, DS., Gupta, P., Zhang, X., Premaratne, P. (eds) Emerging Intelligent Computing Technology and Applications. ICIC 2012. Communications in Computer and Information Science, vol 304. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31837-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-31837-5_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31836-8
Online ISBN: 978-3-642-31837-5
eBook Packages: Computer ScienceComputer Science (R0)