Algorithms for text processing with errors and Uncertainties (Q84225)
Jump to navigation
Jump to search
Project Q84225 in Poland
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Algorithms for text processing with errors and Uncertainties |
Project Q84225 in Poland |
Statements
656,436.0 zloty
0 references
656,436.0 zloty
0 references
100.0 percent
0 references
1 July 2017
0 references
30 June 2019
0 references
UNIWERSYTET WARSZAWSKI
0 references
In pattern matching, it is very common that the input data is corrupted or that we only have an imprecise model of the data. The project focuses on design of efficient algorithms for pattern matching and data structures for indexing for data with errors and uncertainties. Our primary motivation is molecular biology, where several models for uncertain data are used: texts with wildcards, indeterminate texts, weighted sequences (i.e., position weight matrices) and profiles. We consider approximate pattern matching under the Hamming distance and various kinds of approximate periodicities (quasiperiodicities) in texts. We aim at worst-case efficient algorithms; however, recent study in the area of fine-grained complexity suggests that for some of the problems on texts, the state-of-the-art or even naive algorithms are probably optimal. We also aim at experimental verification of our approaches. (Polish)
0 references
In pattern matching, it is very common that the input data is corrupted or that we only have an imprecise model of the data. The project focuses on design of efficient algorithms for pattern matching and data structures for indexing for data with errors and Uncertainties. Our primary motivation is molecular biology, where several models for uncertain data are used: texts with wildcards, indeterminate texts, weighted sequences (i.e., position weight matrices) and profiles. We consider approximate pattern matching under the Hamming distance and various kinds of approximate periodicities (quasiperiodicities) in texts. We aim at worst-case efficient algorithms; however, recent study in the area of fine-grained complexity suggests that for some of the problems on texts, the state-of-the-art or even naive algorithms are probably optimal. We also aim at experimental verification of our approaches. (English)
14 October 2020
0 references
Dans l’appariement des modèles, il est très fréquent que les données d’entrée soient corrompues ou que nous n’ayons qu’un modèle imprécis des données. Le projet se concentre sur la conception d’algorithmes efficaces pour l’appariement des modèles et de structures de données pour l’indexation des données avec des erreurs et des incertitudes. Notre principale motivation est la biologie moléculaire, où plusieurs modèles de données incertaines sont utilisés: textes avec caractères génériques, textes indéterminés, séquences pondérées (c.-à-d. matrices de poids de position) et profils. Nous considérons l’appariement approximatif des patrons sous la distance Hamming et divers types de périodicités approximatives (quasipériodicités) dans les textes. Nous visons des algorithmes efficaces dans le pire des cas; cependant, une étude récente dans le domaine de la complexité à grains fins suggère que pour certains des problèmes sur les textes, les algorithmes de pointe ou même naïfs sont probablement optimaux. Nous visons également la vérification expérimentale de nos approches. (French)
30 November 2021
0 references
Identifiers
POIR.04.04.00-00-24BA/16
0 references