Extensión de secuencias de Bruijn en alfabetos más grandes

Mostrar todas las versiones(3)

Un secuencia circular de Bruijn de orden n en k colores es una secuencia en la que cada palabra de longitud n ocurre exactamente una vez. En esta tesis demostramos que para cada secuencia circular de Bruijn v de orden n en k colores hay otra secuencia circular de Bruijn w de orden n pero en k + 1 co...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Cortés, Lucas
Otros Autores: Becher, Verónica Andrea
Formato: Tesis de grado publishedVersion
Lenguaje:Inglés
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2018
Materias:
SECUENCIAS DE BRUIJN
CICLOS EULERIANOS
BRUIJN SEQUENCES
EULERIAN CYCLES
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id seminario:seminario_nCOM000446_Cortes
record_format dspace
spelling seminario:seminario_nCOM000446_Cortes2023-09-12T13:13:16Z Extensión de secuencias de Bruijn en alfabetos más grandes Extending de Bruijn sequences to larger alphabets Cortés, Lucas Becher, Verónica Andrea SECUENCIAS DE BRUIJN CICLOS EULERIANOS BRUIJN SEQUENCES EULERIAN CYCLES Un secuencia circular de Bruijn de orden n en k colores es una secuencia en la que cada palabra de longitud n ocurre exactamente una vez. En esta tesis demostramos que para cada secuencia circular de Bruijn v de orden n en k colores hay otra secuencia circular de Bruijn w de orden n pero en k + 1 colores tal que v es una subsecuencia de w y entre cualesquiera dos ocurrencias sucesivas del nuevo símbolo en w hay a lo sumo n + 2k − 2 símbolos consecutivos de v. Damos un algoritmo que recibe una tal secuencia v y produce la secuencia w. Damos además un algoritmo mucho más rápido que recibe una tal secuencia v y produce una secuencia w pero sin la garantía de que el nuevo símbolo esté balanceado. A circular de Bruijn sequence of order n in k colors is a sequence in which every possible word of length n occurs exactly once. In this thesis we show that for any given circular de Bruijn sequence v of order n in k colors there is another circular de Bruijn sequence w of order n but in k + 1 colors such that v is a subsequence of w and such that in between two successive occurrences of the new colored symbol in w there are at most n + 2k − 2 consecutive symbols of v. We provide an algorithm that given such an input sequence v produces the output sequence w. And we give a much faster algorithm that also receives as input such a sequence v and outputs a sequence w without the guarantee of the fair distribution of the new colored symbol. Fil: Cortés, Lucas. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2018-12-13 info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
topic SECUENCIAS DE BRUIJN
CICLOS EULERIANOS
BRUIJN SEQUENCES
EULERIAN CYCLES
spellingShingle SECUENCIAS DE BRUIJN
CICLOS EULERIANOS
BRUIJN SEQUENCES
EULERIAN CYCLES
Cortés, Lucas
Extensión de secuencias de Bruijn en alfabetos más grandes
topic_facet SECUENCIAS DE BRUIJN
CICLOS EULERIANOS
BRUIJN SEQUENCES
EULERIAN CYCLES
description Un secuencia circular de Bruijn de orden n en k colores es una secuencia en la que cada palabra de longitud n ocurre exactamente una vez. En esta tesis demostramos que para cada secuencia circular de Bruijn v de orden n en k colores hay otra secuencia circular de Bruijn w de orden n pero en k + 1 colores tal que v es una subsecuencia de w y entre cualesquiera dos ocurrencias sucesivas del nuevo símbolo en w hay a lo sumo n + 2k − 2 símbolos consecutivos de v. Damos un algoritmo que recibe una tal secuencia v y produce la secuencia w. Damos además un algoritmo mucho más rápido que recibe una tal secuencia v y produce una secuencia w pero sin la garantía de que el nuevo símbolo esté balanceado.
author2 Becher, Verónica Andrea
author_facet Becher, Verónica Andrea
Cortés, Lucas
format Tesis de grado
Tesis de grado
publishedVersion
author Cortés, Lucas
author_sort Cortés, Lucas
title Extensión de secuencias de Bruijn en alfabetos más grandes
title_short Extensión de secuencias de Bruijn en alfabetos más grandes
title_full Extensión de secuencias de Bruijn en alfabetos más grandes
title_fullStr Extensión de secuencias de Bruijn en alfabetos más grandes
title_full_unstemmed Extensión de secuencias de Bruijn en alfabetos más grandes
title_sort extensión de secuencias de bruijn en alfabetos más grandes
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2018
url https://hdl.handle.net/20.500.12110/seminario_nCOM000446_Cortes
work_keys_str_mv AT corteslucas extensiondesecuenciasdebruijnenalfabetosmasgrandes
AT corteslucas extendingdebruijnsequencestolargeralphabets
_version_ 1782031585312243712

Ejemplares similares