Thèse de Doctorat
DOI
10.11606/T.45.2012.tde-12092012-230830
Document
Auteur
Nom complet
Francisco Eloi Soares de Araujo
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2012
Directeur
Jury
Soares, Jose Augusto Ramos (Président)
Dias, Zanoni
Ferreira, Carlos Eduardo
Martinez, Fabio Henrique Viduani
Rozante, Luiz Carlos da Silva
Titre en portugais
Alinhamentos e comparação de sequências
Mots-clés en portugais
alinhamento de sequências
alinhamento de várias sequências.
alinhamento estendido
distância de edição
matrizes equivalentes
métrica
Resumé en portugais
Titre en anglais
Alignment and comparison of sequences
Mots-clés en anglais
edit distance
equivalent matrices
extended alignment
metric
multiple sequence alignments.
normalized alignment cost
sequence alignment
Resumé en anglais
Comparison of finite sequences is a tool used to solve problems in several areas. In order to compare sequences, we infer which are the edit operations of substitution, insertion and deletion of symbols that transform one sequence into another. Scoring matrices are a widely used structure to define a cost for each type of edit operation. A scoring matrix G is indexed by symbols of an alphabet. The entry in G in row A and column B measures the cost of the edit operation for replacing symbol A by symbol B. Scoring matrices induce functions that assign a score for a set of edit operations. Some of these functions for comparing two and multiple sequences are studied in this thesis. If each symbol is edited exactly once for transforming a sequence into another, the set of edit operations can be represented by a structure called alignment. We describe a structure to represent the set of edit operations that cannot be represented by a conventional alignment and we design an algorithm to find the cost of an optimal sequence of edit operations by using a known algorithm to find the cost of an optimal alignment. Considering three different kinds of induced scoring functions, we characterize, for each one of them, the class of matrices for which the induced scoring functions are metrics on sequences. Given two scoring matrices G and G', we say they are equivalent for a given function that is induced by a scoring matrix and that evaluates the quality of an alignment if, for any two alignments A and B of two sequences, we have the following: alignment A is ``better'' than B considering scoring matrix G if and only if A is ``better'' than B considering scoring matrix G'. In this work, we determine necessary and sufficient conditions for scoring matrices to be equivalent. Finally, we define three new criteria for scoring alignments of several sequence. Every criterion considers the length of the alignment and the edit operations represented by it. An algorithm for each criterion is studied and the corresponding decision problem is shown to be NP-complete.

AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2012-09-13

AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2023. Tous droits réservés.