Algorithms for text processing with errors and Uncertainties (Q84225): Difference between revisions
Jump to navigation
Jump to search
(Changed an Item: Import item from Poland) |
(Changed an Item: Import item from Poland) |
||||||||||
| Property / coordinate location | |||||||||||
54°24'47.23"N, 18°32'5.06"E
| |||||||||||
| Property / coordinate location: 54°24'47.23"N, 18°32'5.06"E / rank | |||||||||||
Normal rank | |||||||||||
| Property / coordinate location: 54°24'47.23"N, 18°32'5.06"E / qualifier | |||||||||||
| Property / contained in NUTS | |||||||||||
| Property / contained in NUTS: Trójmiejski / rank | |||||||||||
Normal rank | |||||||||||
Revision as of 14:23, 25 October 2022
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
I mønster matchning er det meget almindeligt, at inputdataene er beskadiget, eller at vi kun har en upræcis model af dataene. Projektet fokuserer på design af effektive algoritmer til mønstermatching og datastrukturer til indeksering af data med fejl og usikkerhed. Vores primære motivation er molekylærbiologi, hvor der anvendes flere modeller for usikre data: tekster med wildcards, ubestemte tekster, vægtede sekvenser (dvs. position vægt matricer) og profiler. Vi overvejer omtrentligt mønster matchende under Hamming afstand og forskellige former for omtrentlige hyppigheder (kvasiperiodicities) i tekster. Vi sigter mod de værst tænkelige effektive algoritmer; den seneste undersøgelse inden for finkornet kompleksitet tyder imidlertid på, at de nyeste eller endda naive algoritmer sandsynligvis er optimale for nogle af problemerne med teksterne. Vi sigter også mod eksperimentel kontrol af vores tilgange. (Danish)
26 July 2022
0 references
Στην αντιστοίχιση προτύπων, είναι πολύ σύνηθες ότι τα δεδομένα εισόδου είναι αλλοιωμένα ή ότι έχουμε μόνο ένα ανακριβές μοντέλο των δεδομένων. Το έργο επικεντρώνεται στον σχεδιασμό αποτελεσματικών αλγορίθμων για την αντιστοίχιση προτύπων και δομών δεδομένων για την ευρετηρίαση δεδομένων με σφάλματα και αβεβαιότητες. Το κύριο κίνητρό μας είναι η μοριακή βιολογία, όπου χρησιμοποιούνται διάφορα μοντέλα για αβέβαια δεδομένα: κείμενα με μπαλαντέρ, απροσδιόριστα κείμενα, σταθμισμένες ακολουθίες (δηλ. πίνακες βάρους θέσης) και προφίλ. Εξετάζουμε την κατά προσέγγιση αντιστοίχιση προτύπων κάτω από την απόσταση Hamming και διάφορα είδη κατά προσέγγιση περιοδικότητας (οιονεί περιοδικές) στα κείμενα. Στόχος μας είναι οι πιο αποδοτικοί αλγόριθμοι· ωστόσο, πρόσφατη μελέτη στον τομέα της λεπτής πολυπλοκότητας δείχνει ότι για ορισμένα από τα προβλήματα στα κείμενα, οι υπερσύγχρονοι ή ακόμη και αφελείς αλγόριθμοι είναι πιθανώς βέλτιστοι. Στοχεύουμε επίσης στην πειραματική επαλήθευση των προσεγγίσεων μας. (Greek)
26 July 2022
0 references
U podudaranju uzoraka, vrlo je uobičajeno da su ulazni podaci oštećeni ili da imamo samo neprecizan model podataka. Projekt je usmjeren na dizajn učinkovitih algoritama za usklađivanje uzoraka i struktura podataka za indeksiranje podataka s pogreškama i nesigurnostima. Naša primarna motivacija je molekularna biologija, gdje se koristi nekoliko modela za neizvjesne podatke: tekstovi s zamjenskim znakovima, neodređenim tekstovima, ponderiranim sekvencama (tj. matricama za masu pozicija) i profilima. Smatramo približan uzorak podudaranje pod Hamming udaljenost i razne vrste približne periodičnosti (kvaziperiodicities) u tekstovima. Usmjereni smo na najučinkovitije algoritme u najgorem slučaju; međutim, nedavna studija u području sitnozrnate složenosti sugerira da su za neke od problema na tekstovima, najsuvremeniji ili čak naivni algoritmi vjerojatno optimalni. Cilj nam je i eksperimentalna provjera naših pristupa. (Croatian)
26 July 2022
0 references
În potrivirea modelelor, este foarte comun faptul că datele de intrare sunt corupte sau că avem doar un model imprecis al datelor. Proiectul se concentrează pe proiectarea de algoritmi eficienți pentru corelarea modelelor și structuri de date pentru indexarea datelor cu erori și incertitudini. Motivația noastră principală este biologia moleculară, unde sunt utilizate mai multe modele pentru date incerte: texte cu metacaractere, texte nedeterminate, secvențe ponderate (adică matrice de greutate de poziție) și profile. Considerăm că modelul aproximativ se potrivește sub distanța Hamming și diferite tipuri de periodicități aproximative (cvasiperiodicități) în texte. Urmărim algoritmi eficienți în cel mai rău caz; cu toate acestea, un studiu recent în domeniul complexității granulate sugerează că, pentru unele dintre problemele legate de texte, algoritmii de ultimă generație sau chiar naivi sunt probabil optimi. De asemenea, urmărim verificarea experimentală a abordărilor noastre. (Romanian)
26 July 2022
0 references
Pri zoraďovaní vzorov je veľmi bežné, že vstupné údaje sú poškodené alebo že máme len nepresný model údajov. Projekt sa zameriava na návrh efektívnych algoritmov pre zoraďovanie vzorov a dátových štruktúr pre indexovanie dát s chybami a neistotami. Našou primárnou motiváciou je molekulárna biológia, kde sa používa niekoľko modelov pre neisté údaje: texty so zástupnými znakmi, neurčité texty, vážené sekvencie (t. j. matice hmotnosti polohy) a profily. V textoch považujeme približnú zhodu vzorov pod Hammingovou vzdialenosťou a rôzne druhy približných periodicít (kváziperiodicities). Zameriavame sa na najhorší prípad efektívnych algoritmov; nedávna štúdia v oblasti jemnozrnnej zložitosti však naznačuje, že pri niektorých problémoch v textoch sú najmodernejšie alebo dokonca naivné algoritmy pravdepodobne optimálne. Zameriavame sa aj na experimentálne overovanie našich prístupov. (Slovak)
26 July 2022
0 references
Fit-tqabbil tal-mudell, huwa komuni ħafna li d-data tal-input hija korrotta jew li għandna biss mudell impreċiż tad-data. Il-proġett jiffoka fuq it-tfassil ta’ algoritmi effiċjenti għat-tqabbil tal-mudelli u l-istrutturi tad-data għall-indiċjar għal data bi żbalji u Inċertezza. Il-motivazzjoni primarja tagħna hija l-bijoloġija molekulari, fejn jintużaw diversi mudelli għal data inċerta: testi b’wildcards, testi indeterminati, sekwenzi peżati (jiġifieri, matriċijiet tal-piż tal-pożizzjoni) u profili. Aħna nikkunsidraw mudell approssimattiv tqabbil taħt id-distanza Hamming u diversi tipi ta ‘perjodiki approssimattivi (kważi perjodiċitajiet) fit-testi. Aħna nimmiraw lejn l-agħar algoritmi effiċjenti; madankollu, studju reċenti fil-qasam tal-kumplessità fina jissuġġerixxi li għal xi wħud mill-problemi dwar it-testi, l-algoritmi l-aktar avvanzati jew saħansitra naive huma probabbilment ottimali. Aħna nimmiraw ukoll lejn verifika sperimentali tal-approċċi tagħna. (Maltese)
26 July 2022
0 references
Na correspondência de padrões, é muito comum que os dados de entrada estejam corrompidos ou que tenhamos apenas um modelo impreciso dos dados. O projeto centra-se na conceção de algoritmos eficientes para correspondência de padrões e estruturas de dados para indexação de dados com erros e incertezas. Nossa principal motivação é a biologia molecular, onde vários modelos para dados incertos são usados: textos com curingas, textos indeterminados, sequências ponderadas (ou seja, matrizes de peso de posição) e perfis. Consideramos a correspondência de padrões aproximados sob a distância de Hamming e vários tipos de periodicidades aproximadas (quaseperiodicidades) em textos. Visamos algoritmos eficientes na pior das hipóteses; no entanto, estudos recentes na área de complexidade de grãos finos sugerem que, para alguns dos problemas em textos, os algoritmos de última geração ou até mesmo ingênuos são provavelmente ótimos. Também visamos a verificação experimental das nossas abordagens. (Portuguese)
26 July 2022
0 references
Kuvioiden yhteensovittamisessa on hyvin yleistä, että syöttötiedot ovat vioittuneita tai että meillä on vain epätäsmällinen malli tiedoista. Hankkeessa keskitytään tehokkaiden algoritmien suunnitteluun kuvioiden sovittamista varten ja tietorakenteisiin virheellisten ja epävarmojen tietojen indeksointia varten. Ensisijainen motivaatiomme on molekyylibiologia, jossa käytetään useita malleja epävarmaan dataan: tekstit, joissa on jokerimerkkejä, määrittelemättömiä tekstejä, painotettuja sekvenssejä (eli positiopainomatriisit) ja profiileja. Pidämme likimääräistä kaavaa matching alle Hamming etäisyys ja erilaisia likimääräisiä jaksot (quasi periodicities) teksteissä. Tavoitteenamme ovat pahimmassa tapauksessa tehokkaat algoritmit; viimeaikainen tutkimus hienojakoisesta monimutkaisuudesta viittaa kuitenkin siihen, että joidenkin tekstiin liittyvien ongelmien kohdalla huipputason tai jopa naiivin algoritmit ovat todennäköisesti optimaaleja. Tavoitteenamme on myös kokeiluluontoinen todentaminen lähestymistavoistamme. (Finnish)
26 July 2022
0 references
Pri ujemanju vzorcev je zelo pogosto, da so vhodni podatki poškodovani ali da imamo le nenatančen model podatkov. Projekt se osredotoča na oblikovanje učinkovitih algoritmov za ujemanje vzorcev in podatkovnih struktur za indeksiranje podatkov z napakami in negotovostmi. Naša glavna motivacija je molekularna biologija, kjer se uporablja več modelov za negotove podatke: besedila z nadomestnimi znaki, nedoločenimi besedili, ponderiranimi zaporedji (tj. matricami za utež položaja) in profili. Upoštevamo približno ujemanje vzorca pod razdaljo Hamming in različne vrste približnih periodičnosti (kvaziperiodicities) v besedilih. Prizadevamo si za najmanj učinkovite algoritme; vendar nedavna študija na področju drobnozrnate kompleksnosti kaže, da so za nekatere težave pri besedilih najsodobnejši ali celo naivni algoritmi verjetno optimalni. Prizadevamo si tudi za eksperimentalno preverjanje naših pristopov. (Slovenian)
26 July 2022
0 references
Při porovnávání vzorů je velmi běžné, že vstupní data jsou poškozena nebo že máme pouze nepřesný model dat. Projekt se zaměřuje na návrh efektivních algoritmů pro porovnávání vzorů a datových struktur pro indexaci dat s chybami a nejistotami. Naší hlavní motivací je molekulární biologie, kde se používá několik modelů pro nejistá data: texty se zástupnými znaky, neurčité texty, vážené sekvence (tj. matice hmotnosti polohy) a profily. V textech považujeme přibližný vzor odpovídající pod Hammingovou vzdáleností a různé druhy přibližných periodicit (kvasiperiodicities). Zaměřujeme se na nejnepříznivější algoritmy, nicméně nedávná studie v oblasti jemnozrnné složitosti naznačuje, že u některých problémů na textech jsou pravděpodobně optimální nejmodernější nebo dokonce naivní algoritmy. Naším cílem je také experimentální ověření našich přístupů. (Czech)
26 July 2022
0 references
Modelio atitikimo atveju labai dažnai pasitaiko, kad įvestiniai duomenys yra sugadinti arba kad mes turime tik netikslią duomenų modelį. Projekte daugiausia dėmesio skiriama efektyvių algoritmų, skirtų modelių derinimui, ir duomenų struktūrų, skirtų duomenų indeksavimui su klaidomis ir neapibrėžtimis, kūrimui. Mūsų pagrindinė motyvacija yra molekulinė biologija, kurioje naudojami keli neaiškių duomenų modeliai: tekstai su pakaitos kortomis, neapibrėžti tekstai, svertinės sekos (t. y. pozicijos svorio matricos) ir profiliai. Mes manome, kad apytikslis modelis atitikimo pagal Hamming atstumas ir įvairių rūšių apytikslis periodiškumas (quasiperiodicity) tekstuose. Siekiame blogiausiu atveju efektyvių algoritmų; tačiau neseniai atliktas tyrimas smulkiagrūdžio sudėtingumo srityje rodo, kad kai kurioms tekstų problemoms, modernūs ar net naivūs algoritmai tikriausiai yra optimalūs. Mes taip pat siekiame eksperimentinio mūsų metodų tikrinimo. (Lithuanian)
26 July 2022
0 references
Saskaņojot modeli, ir ļoti bieži, ka ievades dati ir bojāti vai ka mums ir tikai neprecīzs datu modelis. Projekta uzmanības centrā ir efektīvu algoritmu izstrāde modeļu saskaņošanai un datu struktūru indeksēšanai attiecībā uz datiem ar kļūdām un neprecizitātēm. Mūsu galvenā motivācija ir molekulārā bioloģija, kurā tiek izmantoti vairāki neskaidru datu modeļi: teksti ar aizstājējzīmēm, nenoteikti teksti, svērtas sekvences (t. i., pozīcijas svara matricas) un profili. Mēs uzskatām, ka aptuvenais modelis saskaņošana zem Hamming attāluma un dažāda veida aptuvenās periodiskuma (kvaziperiodicitātes) tekstos. Mūsu mērķis ir visefektīvākie algoritmi sliktākajā gadījumā; tomēr nesenais pētījums smalkgraudainas sarežģītības jomā liecina, ka attiecībā uz dažām ar tekstiem saistītām problēmām jaunākie vai pat naivi algoritmi, iespējams, ir optimāli. Mūsu mērķis ir arī eksperimentāla mūsu pieeju pārbaude. (Latvian)
26 July 2022
0 references
При съвпадение на моделите е много често, че входящите данни са повредени или че имаме само неточен модел на данните. Проектът е съсредоточен върху разработването на ефективни алгоритми за съпоставяне на модели и структури на данни за индексиране на данни с грешки и неопределености. Основната ни мотивация е молекулярната биология, при която се използват няколко модела за несигурни данни: текстове със заместващи символи, неопределени текстове, претеглени последователности (т.е. матрици за тегло на позицията) и профили. Считаме, че приблизителното съответствие на модела под разстоянието Хаминг и различните видове приблизителни периодичност (квазипериодичност) в текстовете. Ние се стремим към ефективни алгоритми в най-лошия случай; въпреки това, неотдавнашно проучване в областта на фино-зърнестата сложност показва, че за някои от проблемите в текстовете най-съвременните или дори наивните алгоритми вероятно са оптимални. Ние също така се стремим към експериментална проверка на нашите подходи. (Bulgarian)
26 July 2022
0 references
A minta egyezésében nagyon gyakori, hogy a bemeneti adatok sérültek, vagy csak az adatok pontatlan modellje van. A projekt középpontjában olyan hatékony algoritmusok kialakítása áll, amelyek lehetővé teszik a hiba- és bizonytalansági adatok indexálását a mintapárosításhoz és adatstruktúrákhoz. Elsődleges motivációnk a molekuláris biológia, ahol több modellt használnak a bizonytalan adatokra: helyettesítő karakterekkel ellátott szövegek, meghatározatlan szövegek, súlyozott szekvenciák (azaz pozíciósúly-mátrixok) és profilok. A Hamming-távolság és a szövegekben különböző közelítő gyakoriságok (kvázi periodikitások) közötti közelítő minta egyezést fontolgatunk. A legrosszabb esetben hatékony algoritmusokra törekszünk; a finomszemcsés összetettségről szóló közelmúltbeli tanulmány azonban arra enged következtetni, hogy a szövegekkel kapcsolatos problémák némelyike esetében a legkorszerűbb vagy akár naiv algoritmusok valószínűleg optimálisak. Célunk továbbá megközelítéseink kísérleti ellenőrzése. (Hungarian)
26 July 2022
0 references
I meaitseáil patrún, tá sé an-choitianta go bhfuil na sonraí ionchuir truaillithe nó nach bhfuil againn ach samhail imprecise de na sonraí. Díríonn an tionscadal ar dhearadh halgartaim éifeachtach le haghaidh meaitseáil patrún agus struchtúir sonraí le haghaidh innéacsú le haghaidh sonraí a bhfuil earráidí agus neamhchinnteachtaí. Is é ár bpríomhspreagadh bitheolaíocht mhóilíneach, i gcás ina n-úsáidtear roinnt samhlacha le haghaidh sonraí neamhchinnte: téacsanna le saoróga, téacsanna neamhchinntithe, seichimh ualaithe (i.e. maitrísí meáchain suímh) agus próifílí. Breithnímid meaitseáil phatrún neasach faoin achar Hamming agus cineálacha éagsúla de neas-thréimhseachtaí (corasiperiodicities) i dtéacsanna. Tá sé mar aidhm againn halgartaim éifeachtacha cás is measa; mar sin féin, tugann staidéar le déanaí i réimse na castachta fíneáil-grained le fios gur dócha gur fearr is féidir na halgartaim úrscothacha nó fiú naive a bhaint amach i gcás cuid de na fadhbanna ar théacsanna. Tá sé mar aidhm againn freisin fíorú turgnamhach a dhéanamh ar ár gcur chuige. (Irish)
26 July 2022
0 references
I mönstermatchning är det mycket vanligt att indata är skadad eller att vi bara har en otydlig modell av data. Projektet fokuserar på design av effektiva algoritmer för mönstermatchning och datastrukturer för indexering av data med fel och osäkerheter. Vår främsta motivation är molekylärbiologi, där flera modeller för osäker data används: texter med jokertecken, obestämda texter, viktade sekvenser (dvs. positionsviktsmatriser) och profiler. Vi överväger ungefärliga mönstermatchningar under Hamming avstånd och olika typer av ungefärliga periodiciteter (kvasiperiodicities) i texter. Vi strävar efter effektiva algoritmer i värsta fall. men nyligen genomförda studier inom området finkornig komplexitet tyder på att de senaste eller till och med naiva algoritmerna för vissa av problemen med texter förmodligen är optimala. Vi strävar också efter experimentell verifiering av våra metoder. (Swedish)
26 July 2022
0 references
Mustrite sobitamisel on väga tavaline, et sisendandmed on rikutud või et meil on ainult ebatäpne andmete mudel. Projekt keskendub tõhusate algoritmide väljatöötamisele mustrite sobitamiseks ja andmestruktuuride loomiseks andmete indekseerimiseks vigade ja ebakindlusega andmete jaoks. Meie peamine motivatsioon on molekulaarbioloogia, kus kasutatakse mitmeid ebakindlate andmete mudeleid: metamärkidega tekstid, määratlemata tekstid, kaalutud järjestused (st positsioonikaalu maatriksid) ja profiilid. Me leiame ligikaudne muster sobitamine alla Hamming kaugus ja erinevaid ligikaudne perioodilisus (kvaasiperioodilisus) tekstides. Meie eesmärgiks on halvimal juhul tõhusad algoritmid; kuid hiljutine uuring peeneteralise keerukuse valdkonnas viitab sellele, et mõnede tekstidega seotud probleemide puhul on kaasaegsed või isegi naiivsed algoritmid tõenäoliselt optimaalsed. Meie eesmärk on ka oma lähenemisviiside eksperimentaalne kontrollimine. (Estonian)
26 July 2022
0 references
Cały Kraj
0 references
Identifiers
POIR.04.04.00-00-24BA/16
0 references