A carregar...
Publicação
Learning genes from mutated copies: Algorithms and complexity
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.06 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
In our world, data is everywhere. It is transmitted between devices, or simply stored in
the disc. In these two processes, data can be corrupted, simply for a change, erasure, or
even deletion in its content. The generated corrupted sequences are what we call traces
and, sometimes, we only have access to them, leaving the original content unknown. This
is why we study trace reconstruction algorithms, to try to recover the original content
from the corrupted traces, using the minimum traces possible, with high probability. The
problems we will approach are over DNA sequences of biological models.
The main challenge in trace reconstruction is to determine the minimum number of
necessary traces to achieve accurate reconstruction within the upper bounds of 𝑂(𝑛 log(𝑛))
traces and lower bounds of Ω(𝑛 log(𝑛)) traces. In this thesis, we propose the study of
trace reconstruction over DNA biological models. We will study two different settings,
the average-case and worst-case reconstruction and use reconstruction techniques like
mean-based reconstruction. When the analysis is hard or we believe we can achieve better
results, we will resort to genetic algorithms to get better upper bounds.
From this work, we expect to derive rigorous theorems over the sample complexity,
i.e., the optimal number of traces needed for reliable reconstruction of the problems of
trace reconstruction, motivated by the biological models. When the analysis of the models
proves to be very difficult, we will resort to empirical arguments with genetic algorithms.
No nosso mundo, os dados estão em todo o lado. Eles são transmitidos entre dispositivos, ou simplesmente guardados em disco. Nestes dois processos, os dados podem ser cor- rompidos, simplemente por uma mudança, um apagamento, ou uma eliminação do seu conteúdo. As sequências corrompidas geradas são o que chamamos de traços e, às vezes, somente temos acesso a eles, permanecendo o conteúdo original desconhecido. É por isto que são estudados algoritmos de trace reconstruction com o propósito de, através dos traços corrompidos, recuperar o conteúdo original, usando o mínimo de traços possível, com alta probabilidade. Os problemas que iremos abordar, são sobre modelos biológicos, sobre sequências de DNA. O principal desafio em trace reconstruction é determinar o número mínimo de tra- ços necessários para alcançar uma reconstrução precisa, para majorantes na ordem de 𝑂(𝑛 log(𝑛)) e minorantes de Ω(𝑛 log(𝑛)). Nesta tese, nós propomos o estudo de problemas trace reconstruction sobre proble- mas de modelos biológicos de DNA. Nós iremos estudar dois scenários diferentes, o average-case reconstruction e worst-case reconstruction e usar estratégias como mean-based reconstruction. Quando a análise se demonstrar difícil ou acreditamos que conseguimos melhores resultados, utliaremos algoritmos genéticos. Deste trabalho, nós esperamos derivar teoremas rigorosos sobre a complexidade amostral i.e., o número ótimo de traços necessários para uma reconstrução fiável, sobre os problemas de trace reconstruction, motivados por modelos biológicos. Quando esta análise se demonstrar muito difícil,usaremos argumentos empíricos, utilizando redes neuronais.
No nosso mundo, os dados estão em todo o lado. Eles são transmitidos entre dispositivos, ou simplesmente guardados em disco. Nestes dois processos, os dados podem ser cor- rompidos, simplemente por uma mudança, um apagamento, ou uma eliminação do seu conteúdo. As sequências corrompidas geradas são o que chamamos de traços e, às vezes, somente temos acesso a eles, permanecendo o conteúdo original desconhecido. É por isto que são estudados algoritmos de trace reconstruction com o propósito de, através dos traços corrompidos, recuperar o conteúdo original, usando o mínimo de traços possível, com alta probabilidade. Os problemas que iremos abordar, são sobre modelos biológicos, sobre sequências de DNA. O principal desafio em trace reconstruction é determinar o número mínimo de tra- ços necessários para alcançar uma reconstrução precisa, para majorantes na ordem de 𝑂(𝑛 log(𝑛)) e minorantes de Ω(𝑛 log(𝑛)). Nesta tese, nós propomos o estudo de problemas trace reconstruction sobre proble- mas de modelos biológicos de DNA. Nós iremos estudar dois scenários diferentes, o average-case reconstruction e worst-case reconstruction e usar estratégias como mean-based reconstruction. Quando a análise se demonstrar difícil ou acreditamos que conseguimos melhores resultados, utliaremos algoritmos genéticos. Deste trabalho, nós esperamos derivar teoremas rigorosos sobre a complexidade amostral i.e., o número ótimo de traços necessários para uma reconstrução fiável, sobre os problemas de trace reconstruction, motivados por modelos biológicos. Quando esta análise se demonstrar muito difícil,usaremos argumentos empíricos, utilizando redes neuronais.
Descrição
Palavras-chave
trace reconstruction genetic algorithms DNA sequences Upper bounds Lower Bounds