Sequence pattern mining in biochemical data

Abstract

O recente aumento exponencial do número de sequências genéticas acessíveis através de bases de dados especializadas na internet apresenta grandes decanos para a comunidade científica. Um desses decanos consiste na pesquisa eficiente e efectiva de padrões sequenciais, também chamados motins, entre um conjunto de sequencias de proteínas relacionadas. Tais padrões descrevem regiões que podem fornecer importantes indicações sobre a estrutura e funcionalidade das proteínas analisadas. Considerando os actuais avanços computacionais, e agora possível gerar simulações em larga escala do desenrolamento (holding") de proteínas. A análise dos dados referentes as estas simulações, para compreensão dos mecanismos das proteínas, representa outro desato de investigação. Esta tese aborda estes dois problemas. Quanto ao primeiro, foi dado ^ênfase ao desenvolvimento de algoritmos eficientes que suportam vários tipos de restrições e extraem diferentes tipos de padrões. Foram também estudadas a adequabilidade de diferentes medidas de significância na detecção de padrões relevantes e a aplicabilidade dos mesmos em dois contextos de classificação de sequências. Relativamente ao segundo problema, foi proposto um algoritmo de detecção de padrões aproximados os quais detectam comportamentos similares ou simétricos dos amimo ácidos durante determinados períodos da simulação. Para as diferentes propostas, os detalhes de implementação foram descritos e um conjunto de experiências realizado. Foi demonstrada uma melhoria de desempenho em relação a abordagens anteriores bem como a utilidade destas mesmas propostas na análise de dados bioquímicos.

The recent increase in the number of complete genetic sequences freely available through specialized internet databases presents big challenges for the research community. One such challenge is the eficient and efective search of sequence patterns, also known as motifs, among a set of related protein sequences. Such patterns describe regions that may provide important insights about the structural and functional role of proteins. Considering today's computational advances, it is now possible to generate large scale protein unfolding simulations. Analyzing the data resulted from these simulations and understanding the protein mechanisms poses another research challenge. This thesis deals with these two problems. Regarding the first, we focus on the design of eficient algorithms that support several constraints and extract diferent types of patterns. The ability of diferent significance measures to highlight relevant patterns was evaluated and the applicability of sequence patterns in two sequence classification scenarios was explored. For the second problem, we developed an algorithm to extract approximate patterns, which detect similar and eventually symmetric behavior of the amino acids during parts of the simulation. Implementation details have been provided and experiments conducted. For each proposal it was demonstrated either a performance improvement over previous approaches or the respective applicability on biochemical data analysis.