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
Bei der Musterabgleichung ist es sehr häufig, dass die Eingabedaten beschädigt sind oder dass wir nur ein ungenaues Modell der Daten haben. Das Projekt konzentriert sich auf die Entwicklung effizienter Algorithmen für die Musterabgleichung und Datenstrukturen zur Indexierung von Daten mit Fehlern und Unsicherheiten. Unsere Hauptmotivation ist die Molekularbiologie, in der mehrere Modelle für unsichere Daten verwendet werden: Texte mit Platzhaltern, unbestimmten Texten, gewichteten Sequenzen (d. h. Positionsgewichtsmatrizen) und Profilen. Wir betrachten ungefähre Musterabgleich unter der Hamming-Abstand und verschiedene Arten von ungefähren Periodizitäten (Quasiperioden) in Texten. Wir zielen auf Worst-Case-Effizienzalgorithmen ab; die jüngste Studie im Bereich der feinkörnigen Komplexität legt jedoch nahe, dass bei einigen der Probleme bei Texten der Stand der Technik oder sogar naive Algorithmen wahrscheinlich optimal sind. Darüber hinaus streben wir eine experimentelle Verifizierung unserer Ansätze an. (German)
7 December 2021
0 references
In patroonmatching is het heel gebruikelijk dat de inputgegevens beschadigd zijn of dat we alleen een onnauwkeurig model van de gegevens hebben. Het project richt zich op het ontwerpen van efficiënte algoritmen voor het matchen van patronen en datastructuren voor het indexeren van gegevens met fouten en onzekerheden. Onze primaire motivatie is moleculaire biologie, waarbij verschillende modellen voor onzekere gegevens worden gebruikt: teksten met wildcards, onbepaalde teksten, gewogen sequenties (d.w.z. matrices van het positiegewicht) en profielen. We beschouwen bij benadering patroon matching onder de Hamming afstand en verschillende soorten geschatte periodiciteiten (quasiperiodiciteiten) in teksten. We streven naar worst-case efficiënte algoritmen; echter, recente studie op het gebied van fijnkorrelige complexiteit suggereert dat voor sommige van de problemen op teksten, de state-of-the-art of zelfs naïeve algoritmen waarschijnlijk optimaal zijn. We streven ook naar experimentele verificatie van onze benaderingen. (Dutch)
16 December 2021
0 references
Nella corrispondenza dei modelli, è molto comune che i dati di input siano corrotti o che abbiamo solo un modello impreciso dei dati. Il progetto si concentra sulla progettazione di algoritmi efficienti per la corrispondenza tra modelli e strutture di dati per l'indicizzazione dei dati con errori e incertezze. La nostra motivazione primaria è la biologia molecolare, dove vengono utilizzati diversi modelli per dati incerti: testi con caratteri jolly, testi indeterminati, sequenze ponderate (vale a dire, matrici di peso di posizione) e profili. Consideriamo la corrispondenza approssimativa del modello sotto la distanza di Hamming e vari tipi di periodicità approssimativa (quasiperiodicities) nei testi. Puntiamo a algoritmi efficienti nel peggiore dei casi; tuttavia, recenti studi nel settore della complessità a grana fine suggeriscono che per alcuni dei problemi sui testi, gli algoritmi all'avanguardia o persino ingenui sono probabilmente ottimali. Puntiamo anche alla verifica sperimentale dei nostri approcci. (Italian)
16 January 2022
0 references
En la coincidencia de patrones, es muy común que los datos de entrada están dañados o que solo tenemos un modelo impreciso de los datos. El proyecto se centra en el diseño de algoritmos eficientes para la correspondencia de patrones y estructuras de datos para la indexación de datos con errores e incertidumbres. Nuestra motivación principal es la biología molecular, donde se utilizan varios modelos de datos inciertos: textos con comodines, textos indeterminados, secuencias ponderadas (es decir, matrices de peso de posición) y perfiles. Consideramos la coincidencia de patrones aproximados bajo la distancia Hamming y varios tipos de periodicidades aproximadas (cuasiperiodicidades) en los textos. Nuestro objetivo es lograr algoritmos eficientes en el peor de los casos; sin embargo, estudio reciente en el área de la complejidad de grano fino sugiere que para algunos de los problemas en los textos, el estado de la técnica o incluso algoritmos ingenuos son probablemente óptimos. También aspiramos a la verificación experimental de nuestros enfoques. (Spanish)
19 January 2022
0 references
Identifiers
POIR.04.04.00-00-24BA/16
0 references