PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of amolbioBioMed CentralBiomed Central Web Sitesearchsubmit a manuscriptregisterthis articleAlgorithms for Molecular Biology : AMB
 
Algorithms Mol Biol. 2012; 7: 10.
Published online May 2, 2012. doi:  10.1186/1748-7188-7-10
PMCID: PMC3402988
Pattern matching through Chaos Game Representation: bridging numerical and discrete data structures for biological sequence analysis
Susana Vinga,corresponding author1,2 Alexandra M Carvalho,3,4 Alexandre P Francisco,1,4 Luís MS Russo,1,4 and Jonas S Almeida5
1Instituto de Engenharia de Sistemas e Computadores: Investigação e Desenvolvimento (INESC-ID), R. Alves Redol 9, 1000-029 Lisboa, Portugal
2Dept Bioestatística e Informática, Faculdade de Ciências Médicas - Universidade Nova de Lisboa (FCM/UNL), C. Mártires Pátria 130, 1169-056 Lisboa, Portugal
3Instituto de Telecomunicações (IT), Av. Rovisco Pais 1, Torre Norte, Piso 10, 1049-001 Lisboa, Portugal
4Instituto Superior Técnico, Universidade Técnica de Lisboa (IST/UTL), Av. Rovisco Pais 1, 1049-001 Lisboa, Portugal
5Div Informatics, Dept Pathology, University of Alabama at Birmingham, USA
corresponding authorCorresponding author.
Susana Vinga: svinga/at/kdbio.inesc-id.pt; Alexandra M Carvalho: asmc/at/lx.it.pt; Alexandre P Francisco: aplf/at/inesc-id.pt; Luís MS Russo: luis.russo/at/ist.utl.pt; Jonas S Almeida: jalmeida/at/mathbiol.org
Received January 25, 2012; Accepted May 2, 2012.
Abstract
Background
Chaos Game Representation (CGR) is an iterated function that bijectively maps discrete sequences into a continuous domain. As a result, discrete sequences can be object of statistical and topological analyses otherwise reserved to numerical systems. Characteristically, CGR coordinates of substrings sharing an L-long suffix will be located within 2-L distance of each other. In the two decades since its original proposal, CGR has been generalized beyond its original focus on genomic sequences and has been successfully applied to a wide range of problems in bioinformatics. This report explores the possibility that it can be further extended to approach algorithms that rely on discrete, graph-based representations.
Results
The exploratory analysis described here consisted of selecting foundational string problems and refactoring them using CGR-based algorithms. We found that CGR can take the role of suffix trees and emulate sophisticated string algorithms, efficiently solving exact and approximate string matching problems such as finding all palindromes and tandem repeats, and matching with mismatches. The common feature of these problems is that they use longest common extension (LCE) queries as subtasks of their procedures, which we show to have a constant time solution with CGR. Additionally, we show that CGR can be used as a rolling hash function within the Rabin-Karp algorithm.
Conclusions
The analysis of biological sequences relies on algorithmic foundations facing mounting challenges, both logistic (performance) and analytical (lack of unifying mathematical framework). CGR is found to provide the latter and to promise the former: graph-based data structures for sequence analysis operations are entailed by numerical-based data structures produced by CGR maps, providing a unifying analytical framework for a diversity of pattern matching problems.
Articles from Algorithms for Molecular Biology : AMB are provided here courtesy of
BioMed Central