Um algoritmo quase-linear para arvores PQR e um esquema para clustering de sequencias expressas de cana-de-açucar

AUTOR(ES)
DATA DE PUBLICAÇÃO

2002

RESUMO

Nesta tese apresentamos um algoritmo quase-linear para construir árvores PQR e o esquema para clustering de seqüências expressas que foi usado no projeto SUCEST (Sugarcane EST project).Uma árvore PQR é uma estrutura de dados capaz de resolver o problema dos uns consecutivos e outros problemas, como mapeamento físico de DNA, reconhecimento de grafos intervalo, otimização de circuitos lógicos e recuperação de dados. As árvores PQR são uma generalização das árvores PQ de Booth e Lueker e estão fundamentadas em propriedades algébricas sólidas. O algoritmo que apresentamos nesta tese se baseia nessas propriedades e é formado por um conjunto pequeno de padrões que modificam a árvore. Nosso algoritmo é mais eficiente que o algoritmo quadrático proposto originalmente por Meidanis e Munuera ao definir as árvores PQR e, embora não seja linear como o algoritmo para construir árvores PQ, acreditamos que ele contribui em direção a uma solução definitiva para o problema dos uns consecutivos. Clustering é o problema de categorização de um conjunto de objetos quando nem o número nem a composição das categorias é conhecido antecipadamente. Seqüências expressas ou ESTs (expressed sequence tags) são amostras de genes ativos extraídas das células de um organismo. Em um projeto genoma EST são obtidas milhares dessas seqüências que serão usadas como fonte para investigações por cientistas interessados nos processos celulares do organismo. O clustering de seqüências expressas é necessário para avaliar e reduzir a redundância do conjunto de ESTs. Nesta tese apresentamos o esquema de clustering usado no projeto da cana-de-açúcar, que produziu aproximadamente 300.000 ESTs. O esquema que apresentamos substituiu um esquema pré-existente e se caracteriza por uma limpeza prévia intensiva dos ESTs e pelo uso de um montador de genomas para agrupá-los. Acreditamos que este esquema possa ser utilizado em outros projetos do gênero

ASSUNTO(S)

genomas algoritmos cana-de-açucar estruturas de dados (computação) sequencia de nucleotidios

ACESSO AO ARTIGO

Documentos Relacionados