Registro fonte: Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear

Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear

Bioinformatics is an application of computational, statistical and mathematical techniques for the analysis, interpretation and control of biological data, mainly related to genetics. A frequent tasks in this area is the sequence alignment, which uses a cost function to present an optimum alignment...

ver descrição completa

Autor principal:	Costacurta, Matheus
Formato:	Trabalho de Conclusão de Curso (Graduação)
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2020
Assuntos:	Bioinformática Complexidade computacional Algorítmos Bioinformatics Computational complexity Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/15987
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-15987
recordtype	dspace
spelling	riut-1-159872020-11-19T18:24:53Z Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear Global alignments of two genetic sequences: optimal results in linear space Costacurta, Matheus Zatesko, Leandro Miranda Almeida, Sheila Morais de Zatesko, Leandro Miranda Carmo, Renato José da Silva Maciel, Denise do Rocio Bioinformática Complexidade computacional Algorítmos Bioinformatics Computational complexity Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Bioinformatics is an application of computational, statistical and mathematical techniques for the analysis, interpretation and control of biological data, mainly related to genetics. A frequent tasks in this area is the sequence alignment, which uses a cost function to present an optimum alignment between related sequences. This task is frequent since it is used to compare genetic material and to construct the taxonomy of living beings. The space complexity of the known exact algorithms to present more than one optimum alignment between two genetic sequences is 𝑂(𝑚𝑛), where 𝑚 and 𝑛 are the sizes of the two sequences given by the number of base pairs. This space complexity may be unwanted, since the size of the sequences can reach millions of bases. Hence, many authors use heuristics, more efficient in the use of space, but without the certainty of optimality. This work, however, aims to develop a linear space complexity exact algorithm to find more than one optimum alignment between two genetic sequences. A Bioinformática é a aplicação de técnicas computacionais, matemáticas e estatísticas para analisar, interpretar e processar dados biológicos, principalmente dados relacionados a genética. Uma tarefa frequente nessa área é o alinhamento de sequências, que utiliza uma função de custo para apresentar o alinhamento ótimo entre sequências relacionadas. Esta tarefa é frequente por ser utilizada para comparação de material genético e construção da taxonomia de seres vivos. A complexidade de espaço dos algoritmos exatos conhecidos que apresentam mais que um alinhamento ótimo entre duas sequências genéticas é 𝑂(𝑚𝑛), sendo 𝑚 e 𝑛 os tamanhos das duas sequências em pares de bases. Essa complexidade de espaço pode ser indesejada, visto que o tamanho das sequências pode chegar a milhões de bases. Por isso, muitos autores utilizam heurísticas, mais eficientes no uso do espaço, porém sem a garantia de uma solução ótima. O presente trabalho, contudo, tem como objetivo desenvolver um algoritmo exato com complexidade de espaço linear para encontrar mais que um alinhamento ótimo entre duas sequências genéticas. 2020-11-19T18:24:53Z 2020-11-19T18:24:53Z 2019-11-25 bachelorThesis COSTACURTA, Matheus. Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear. 2019. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2019. http://repositorio.utfpr.edu.br/jspui/handle/1/15987 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Ponta Grossa Brasil Departamento Acadêmico de Informática Ciência da Computação UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Bioinformática Complexidade computacional Algorítmos Bioinformatics Computational complexity Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
spellingShingle	Bioinformática Complexidade computacional Algorítmos Bioinformatics Computational complexity Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Costacurta, Matheus Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear
description	Bioinformatics is an application of computational, statistical and mathematical techniques for the analysis, interpretation and control of biological data, mainly related to genetics. A frequent tasks in this area is the sequence alignment, which uses a cost function to present an optimum alignment between related sequences. This task is frequent since it is used to compare genetic material and to construct the taxonomy of living beings. The space complexity of the known exact algorithms to present more than one optimum alignment between two genetic sequences is 𝑂(𝑚𝑛), where 𝑚 and 𝑛 are the sizes of the two sequences given by the number of base pairs. This space complexity may be unwanted, since the size of the sequences can reach millions of bases. Hence, many authors use heuristics, more efficient in the use of space, but without the certainty of optimality. This work, however, aims to develop a linear space complexity exact algorithm to find more than one optimum alignment between two genetic sequences.
format	Trabalho de Conclusão de Curso (Graduação)
author	Costacurta, Matheus
author_sort	Costacurta, Matheus
title	Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear
title_short	Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear
title_full	Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear
title_fullStr	Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear
title_full_unstemmed	Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear
title_sort	alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2020
citation	COSTACURTA, Matheus. Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear. 2019. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2019.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/15987
_version_	1805303464200241152
score	10,814766

Alinhamentos globais de duas sequências genéticas: resultados ótimos em espaço linear

Registros relacionados