Operations on trajectories with applications to coding and bioinformatics
Result description
We study binary word operations of the insertion, deletion and substitution type. Many of these operations can be generalized into a unified framework by introducing so-called trajectory condition. This generalization has been previously made for insertion and deletion operations. In this paper we naturally extend this approach also to substitution operations. We study closure properties and decision problems of substitutions on trajectories. The obtained results are then applied to model complex noisychannels and a cryptanalysis problem. Another application concerns the design of sets of DNA strands without undesired bonds.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Operations on trajectories with applications to coding and bioinformatics
Original language description
We study binary word operations of the insertion, deletion and substitution type. Many of these operations can be generalized into a unified framework by introducing so-called trajectory condition. This generalization has been previously made for insertion and deletion operations. In this paper we naturally extend this approach also to substitution operations. We study closure properties and decision problems of substitutions on trajectories. The obtained results are then applied to model complex noisychannels and a cryptanalysis problem. Another application concerns the design of sets of DNA strands without undesired bonds.
Czech name
Operace na trajektoriích s aplikacemi v kódování a bioinformatice
Czech description
Studujeme binární operace typu vkládání, mazání a substituce nad slovy. Mnohé z těchto operací mohou být zobecněny do jednotného rámce pomocí zavedení syntaktických omezujících podmínek - tzv. trajektorií. Soustředíme se zejména na uzávěrové vlastnosti arozhodovací problémy spojené se substitucí na trajektoriích. Výsledky jsou aplikovány v modelování přenosových kanálů se šumem a na problém kryptoanalýzy. Další aplikace nacházejí při návrhu množin DNA molekul bez nežádoucích vazeb.
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
ISSN
0129-0541
e-ISSN
—
Volume of the periodical
3
Issue of the periodical within the volume
16
Country of publishing house
SG - SINGAPORE
Number of pages
16
Pages from-to
—
UT code for WoS article
—
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
IN - Informatics
Year of implementation
2005