A5000458313- semigroups and automata theory
- Algorithms and Data Compression
- DNA and Biological Computing
- Optimization and Packing Problems
- Natural Language Processing Techniques
- Computational Geometry and Mesh Generation
- Coding theory and cryptography
- Advanced Manufacturing and Logistics Optimization
- Cellular Automata and Applications
- Graph Theory and Algorithms
- Authorship Attribution and Profiling
- Complexity and Algorithms in Graphs
- Optimization and Search Problems
- Network Packet Processing and Optimization
- Digital Image Processing Techniques
- Parallel Computing and Optimization Techniques
- Rough Sets and Fuzzy Logic
- Data Management and Algorithms
- RNA and protein synthesis mechanisms
- Advanced Graph Theory Research
- graph theory and CDMA systems
- Logic, programming, and type systems
- Genomics and Phylogenetic Studies
- Advanced Optimization Algorithms Research
- Advanced Scientific Research Methods
Lomonosov Moscow State University
2013-2024
Dorodnitsyn Computing Centre
2016-2024
Russian Academy of Sciences
2017-2024
Moscow State University
2016-2024
National Research University of Electronic Technology
2016
University of Liverpool
2003-2005
Institut national de recherche en informatique et en automatique
1998-2001
Laboratoire Lorrain de Recherche en Informatique et ses Applications
2001
Centre Inria de l'Université de Lorraine
2001
The presence of repeated sequences is a fundamental feature genomes. Tandemly DNA appears in both eukaryotic and prokaryotic genomes, it associated with various regulatory mechanisms plays an important role genomic fingerprinting. In this paper, we describe mreps, powerful software tool for fast identification tandemly structures sequences. mreps able to identify all types tandem repeats within single run on whole sequence. It has resolution parameter that allows the program 'fuzzy' repeats....
A repetition in a word w is subword with the period of at most half length. We study maximal repetitions occurring w, that those for which any extended has bigger period. The set such represents compact way all w. first prove combinatorial result asserting sum exponents length n bounded by linear function n. This implies, particular there only number word. allows us to construct linear-time algorithm finding repetitions. Some consequences and applications these results are discussed, as well...
Summary form only given. In text compression applications, it is important to be able process compressed data without requiring (complete) decompression. this context crucial study methods that allow time/space efficient access any fragment of a file being forced perform complete We here the real-time recovery consecutive symbols from files, in grammar-based compression. setting, represented as small (a few Kb) dictionary D (containing set code words), and very long Mb) string based on drawn...
We propose an algorithm for finding, within a word, all pairs of occurrences the same subword given distance r. The obtained complexity is O(n log r + S), where S size output. also show how can be modified in order to find such separated by word. solution uses finding quasi-squares two strings, problem that generalizes well-known searching squares.
Summary In the paper, we compute some lower bounds on time of parallel solving subset sum problem a big number processors by several versions dynamic programming algorithm Balsub proposed before Pisinger. Based these bounds, propose version which could be possibly effectively parallelized.
This paper is devoted to questions concerning the complexity of solution problem on one-dimensional Boolean knapsack by branch and bound method. For this we obtain two upper bounds. We separate special case where polynomially bounded dimension problem. also an lower bounds for method subset sum which a
Packing several characters into one computer word is a simple and natural way to compress the representation of string speed up its processing. Exploiting this idea, we propose an index for packed string, based on {\em sparse suffix tree} \cite{KU-96} with appropriately defined links. Assuming, under standard unit-cost RAM model, that can store $\log_{\sigma}n$ ($\sigma$ alphabet size), our takes $O(n/\log_{\sigma}n)$ space, i.e. same space as itself. The resulting pattern matching algorithm...