Orientador: Guilherme Pimentel TellesDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Na biologia molecular o alinhamento de sequências é uma ferramenta para caracterizar similaridade ou distância entre sequências. O problema do alinhamento restrito por expressão regular (RECSA: Regular Expression Constrained Sequence Alignment) foi proposto no ano de 2005 por Arslan. O alinhamento restrito procura encontrar um alinhamento ótimo entre duas sequências de tal forma que a expressão regular esteja expressa numa parte do alinhamento. Famílias e domínios de proteínas encontram-se caraterizados como padrões no banco de dados PROSITE os quais são usados na biologia molecular para identificar e classificar proteínas. Esses padrões podem ser representados por expressões regulares e usados como restrição no alinhamento de Arslan. Na solução de Arslan para o alinhamento restrito é usado um autômato finito sem transições vazias construído a partir da expressão regular. O tempo de execução dessa solução depende do número de estados e transições desse autômato. Neste trabalho apresentamos quatro resultados. Primeiro, apresentamos um algoritmo melhorado da construção de Thompson que permite construir autômatos finitos mais compactos diretamente da expressão regular em tempo linear. Segundo, apresentamos uma forma de construir expressões regulares equivalentes a padrões PROSITE que, ao serem usadas na construção melhorada de Thompson, geram diretamente autômatos compactos sem transições vazias. Esses autômatos possuem número de estados sublinear e número de transições linear em relação ao número de símbolos da expressão regular, números menores que o esperado ao usar os resultados da literatura. Terceiro, esses autômatos compactos, ao serem usados na solução de Arslan, melhoram naturalmente o tempo de execução, esse tempo também é melhor que as soluções propostas por Chung et al. no ano de 2007 e por Kucherov et al. no ano de 2011. Finalmente, apresentamos um pré-processamento que, ao ser aplicado na solução de Arslan, melhora ainda mais o tempo de execução, conseguindo um limite inferior sobre a complexidade de tempo independente do tamanho do autômatoAbstract: In molecular biology the sequence alignment is a tool for characterizing similarity or distance between sequences. The Regular Expression Constrained Sequence Alignment problem (RECSA) was proposed in 2005 by Arslan. Constrained alignment seeks to find an optimal alignment between two sequences such that the regular expression is expressed in a part of the alignment. Protein families and domains are characterized as patterns in PROSITE database, which are used in molecular biology to identify and classify proteins. These patterns can be represented by regular expressions and used as a restriction on Arslan alignment. In Arslan's solution for constrained alignment a finite automaton without empty transitions constructed from the regular expression is used. The running time of the solution depends on the number of states and transitions of this automaton. In this work we show four results. First, we present an improved Thompson's construction \cite{thompson68} that, allows building a more compact finite automatons directly from the regular expression in linear time. Second, we present a way to build regular expressions equivalent to PROSITE patterns that when used with the improved Thompson construction, generates compact automatons without empty transitions directly. These automatons have a sublinear number of states and a linear number of transitions in relation to the number of symbols in the regular expression, with smaller numbers than expected when compared to the literature results. Third, these compact automatons, when used in Arslan's solution improve runtime naturally and such time is also better than the solutions proposed by Chung et al. in 2007 and by Kucherov et al. in 2011. Finally, we present a preprocessing step which when applied to Arslan's solution improves further the running time, managing to achieve a lower bound on the time complexity independent of the size of the automatonMestradoCiência da ComputaçãoMestre em Ciência da Computação132470/2012-8CNPQ