Spelling suggestions: "subject:"alinhamento dde seqüência"" "subject:"alinhamento dde freqüências""
1 |
Aplicação de algoritmos genéricos multi-objetivo para alinhamento de seqüências biológicas. / Multi-objective genetic algorithms applied to protein sequence alignment.Ticona, Waldo Gonzalo Cancino 26 February 2003 (has links)
O alinhamento de seqüências biológicas é uma operação básica em Bioinformática, já que serve como base para outros processos como, por exemplo, a determinação da estrutura tridimensional das proteínas. Dada a grande quantidade de dados presentes nas seqüencias, são usadas técnicas matemáticas e de computação para realizar esta tarefa. Tradicionalmente, o Problema de Alinhamento de Seqüências Biológicas é formulado como um problema de otimização de objetivo simples, onde alinhamento de maior semelhança, conforme um esquema de pontuação, é procurado. A Otimização Multi-Objetivo aborda os problemas de otimização que possuem vários critérios a serem atingidos. Para este tipo de problema, existe um conjunto de soluções que representam um "compromiso" entre os objetivos. Uma técnica que se aplica com sucesso neste contexto são os Algoritmos Evolutivos, inspirados na Teoria da Evolução de Darwin, que trabalham com uma população de soluções que vão evoluindo até atingirem um critério de convergência ou de parada. Este trabalho formula o Problema de Alinhamento de Seqüências Biológicas como um Problema de Otimização Multi-Objetivo, para encontrar um conjunto de soluções que representem um compromisso entre a extensão e a qualidade das soluções. Aplicou-se vários modelos de Algoritmos Evolutivos para Otimização Multi-Objetivo. O desempenho de cada modelo foi avaliado por métricas de performance encontradas na literatura. / The Biological Sequence Alignment is a basic operation in Bioinformatics since it serves as a basis for other processes, i.e. determination of the protein's three-dimensional structure. Due to the large amount of data involved, mathematical and computational methods have been used to solve this problem. Traditionally, the Biological Alignment Sequence Problem is formulated as a single optimization problem. Each solution has a score that reflects the similarity between sequences. Then, the optimization process looks for the best score solution. The Multi-Objective Optimization solves problems with multiple objectives that must be reached. Frequently, there is a solution set that represents a trade-off between the objectives. Evolutionary Algorithms, which are inspired by Darwin's Evolution Theory, have been applied with success in solving this kind of problems. This work formulates the Biological Sequence Alignment as a Multi-Objective Optimization Problem in order to find a set of solutions that represent a trade-off between the extension and the quality of the solutions. Several models of Evolutionary Algorithms for Multi-Objetive Optimization have been applied and were evaluated using several performance metrics found in the literature.
|
2 |
Alinhamento de seqüências biológicas com o uso de algoritmos genéticos.Ogata, Sabrina Oliveira 14 March 2005 (has links)
Made available in DSpace on 2016-06-02T20:21:33Z (GMT). No. of bitstreams: 1
DissSOO.pdf: 370558 bytes, checksum: eaf0bc7ee24eeffcd23041e4273aa013 (MD5)
Previous issue date: 2005-03-14 / Universidade Federal de Sao Carlos / The comparison of genome sequences from different organisms is one
of the computational application most frequently used by molecular
biologists. This operation serves as support for other processes as, for
instance, the determination of the three- dimensional structure of the
proteins. During the last years, a significative increase has been observed
in the use of Genetic Algorithms (GA) for optimization problems as, for
example, dna or protein sequence alignment. GAs are search techniques
inspired in mechanisms from Natural Selection and Genetics. In this work,
a GA was used to development a computacional tool for the sequence
alignment problem. A benchmark comparison of this program with the
bl2seq tool (from Blast package) is showed using some sequences, varying
in similarity and length. In some cases the GA overhelmed the bl2seq tool.
This work contributes to the Bioinformatic field by the use of a novel
methodology that can use as an option for sequence analysis in genome
projects and to enhance the results of other tools such like Blast. / A comparação de seqüências de genomas de organismos é uma das
aplicações computacionais mais utilizadas por biólogos moleculares. Esta
operação serve de suporte para outros processos como, por exemplo, a
determinação da estrutura tridimensional de proteínas. Durante os últimos
anos, tem- se observado uma grande expansão na utilização de Algoritmos
Evolutivos, especialmente Algoritmos Genéticos (AGs), para problemas de
otimização, como os de alinhamento de seqüências de dna e proteínas. Os
AGs são técnicas de busca inspiradas em mecanismos de seleção natural
e da genética. Neste trabalho, um AG foi utilizado para o desenvolvimento
de uma ferramenta computacional para o problema de alinhamento de
pares de seqüências. Uma comparação foi realizada com o uso da
ferramenta bl2seq (do pacote de ferramentas Blast) afim de se checar a
desempenho do AG. Utilizou- se para isso seqüências de diversos tamanhos
e graus de similaridade. Os resultados demonstraram alguns casos
específicos onde o AG superou a ferramenta bl2seq. A principal
contribuição deste trabalho está na área de Bioinformática, com o
emprego de uma nova metodologia, que posteriormente possa ser
utilizada como mais uma opção para análises de seqüências em projetos
genomas e para refinamento dos resultados obtidos por outras
ferramentas usualmente utilizadas, como o Blast.
|
3 |
Aplicação de algoritmos genéricos multi-objetivo para alinhamento de seqüências biológicas. / Multi-objective genetic algorithms applied to protein sequence alignment.Waldo Gonzalo Cancino Ticona 26 February 2003 (has links)
O alinhamento de seqüências biológicas é uma operação básica em Bioinformática, já que serve como base para outros processos como, por exemplo, a determinação da estrutura tridimensional das proteínas. Dada a grande quantidade de dados presentes nas seqüencias, são usadas técnicas matemáticas e de computação para realizar esta tarefa. Tradicionalmente, o Problema de Alinhamento de Seqüências Biológicas é formulado como um problema de otimização de objetivo simples, onde alinhamento de maior semelhança, conforme um esquema de pontuação, é procurado. A Otimização Multi-Objetivo aborda os problemas de otimização que possuem vários critérios a serem atingidos. Para este tipo de problema, existe um conjunto de soluções que representam um "compromiso" entre os objetivos. Uma técnica que se aplica com sucesso neste contexto são os Algoritmos Evolutivos, inspirados na Teoria da Evolução de Darwin, que trabalham com uma população de soluções que vão evoluindo até atingirem um critério de convergência ou de parada. Este trabalho formula o Problema de Alinhamento de Seqüências Biológicas como um Problema de Otimização Multi-Objetivo, para encontrar um conjunto de soluções que representem um compromisso entre a extensão e a qualidade das soluções. Aplicou-se vários modelos de Algoritmos Evolutivos para Otimização Multi-Objetivo. O desempenho de cada modelo foi avaliado por métricas de performance encontradas na literatura. / The Biological Sequence Alignment is a basic operation in Bioinformatics since it serves as a basis for other processes, i.e. determination of the protein's three-dimensional structure. Due to the large amount of data involved, mathematical and computational methods have been used to solve this problem. Traditionally, the Biological Alignment Sequence Problem is formulated as a single optimization problem. Each solution has a score that reflects the similarity between sequences. Then, the optimization process looks for the best score solution. The Multi-Objective Optimization solves problems with multiple objectives that must be reached. Frequently, there is a solution set that represents a trade-off between the objectives. Evolutionary Algorithms, which are inspired by Darwin's Evolution Theory, have been applied with success in solving this kind of problems. This work formulates the Biological Sequence Alignment as a Multi-Objective Optimization Problem in order to find a set of solutions that represent a trade-off between the extension and the quality of the solutions. Several models of Evolutionary Algorithms for Multi-Objetive Optimization have been applied and were evaluated using several performance metrics found in the literature.
|
4 |
Alinhamento de seqüências com rearranjos / Sequences alignment with rearrangementsVellozo, Augusto Fernandes 18 April 2007 (has links)
Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2). / Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.
|
5 |
Alinhamento de seqüências com rearranjos / Sequences alignment with rearrangementsAugusto Fernandes Vellozo 18 April 2007 (has links)
Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2). / Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.
|
6 |
Alinhamento de seqüências biológicas em arquiteturas com memória distribuídaPeranconi, Daniela Saccol 04 March 2005 (has links)
Made available in DSpace on 2015-03-05T13:53:44Z (GMT). No. of bitstreams: 0
Previous issue date: 4 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A utilização de aglomerados de computadores na solução de problemas que demandam grande quantidade de recursos computacionais vem se mostrando uma alternativa interessante. aglomerados são economicamente viáveis e de fácil manutenção, oferecendo poder computacional equivalente ao de supercomputadores. No entanto,
o desenvolvimento de aplicações para este tipo de arquitetura é complexo, uma vez que envolve questões não presentes na programação seqüencial, como a comunicação de dados e a sincronização de tarefas concorrentes, problemas estes que, em geral, são tratados em supercomputadores por pacotes de software especializados. Neste contexto, este trabalho apresenta o desenvolvimento de um mecanismo de suporte à comunicação sobre aglomerados de computadores, focado na exploração desta plataforma de hardware para o processamento de alto desempenho. O mecanismo criado e disponibilizado sob a forma de uma biblioteca de funções em C, é baseado no modelo de Mensagens
Ativas. Sua implementação é realizada na cama / The use of cluster of computers for solving problems that require a great quantity
of computational resources is becoming an interesting alternative. Clusters are economically
feasible and of easy maintenance, offering a computational power equivalent to that
of supercomputers. However developing applications for this kind of architecture is complex because it involves issues that are not present in the sequential programming such
as data communication and concurrent tasks synchronization, problems that usually are
handled by specialized software packages in supercomputers. Considering this context,
this work presents the development of a mechanism for supporting communication on clusters of computers focused on exploring this hardware platform for high performance processing. The mechanism was created as a library of functions written in C and it is based on the Active Messages model. Its implementation was performed on the applicative level, using light multiprogramming techniques as programming resou
|
Page generated in 0.0677 seconds