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 la correspondance de motifs, il est très courant 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 des 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 la correspondance approximative sous la distance de 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é fine 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
Beim Musterabgleich 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 Musterabgleich und Datenstrukturen zur Indexierung von Daten mit Fehlern und Unsicherheiten. Unsere primäre Motivation 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 die ungefähre Musterabstimmung unter der Hamming-Distanz und verschiedene Arten von ungefähren Periodizitäten (quasiperiodities) in Texten. Wir zielen auf effiziente Algorithmen im schlimmsten Fall ab; eine aktuelle Studie im Bereich der feinkörnigen Komplexität legt jedoch nahe, dass für einige der Probleme bei Texten der Stand der Technik oder sogar naive Algorithmen wahrscheinlich optimal sind. Wir streben auch die experimentelle Überprüfung unserer Ansätze an. (German)
7 December 2021
0 references
In patroon matching is het heel gebruikelijk dat de invoergegevens 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 patroon matching 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. positiegewicht matrices) en profielen. We beschouwen bij benadering patroon matching onder de Hamming afstand en verschillende soorten geschatte periodiciteiten (quasiperiodicities) in teksten. We streven naar worst-case efficiënte algoritmen; recente studie op het gebied van fijnkorrelige complexiteit suggereert echter 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 pattern, è molto comune che i dati di input siano danneggiati o che abbiamo solo un modello impreciso dei dati. Il progetto si concentra sulla progettazione di algoritmi efficienti per la corrispondenza dei 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 (cioè matrici di peso di posizione) e profili. Consideriamo la corrispondenza approssimativa del modello sotto la distanza di Hamming e vari tipi di periodicità approssimativa (quasiperiodicità) nei testi. Miriamo a algoritmi efficienti nel peggiore dei casi; tuttavia, recenti studi nell'area della complessità a grana fine suggeriscono che per alcuni dei problemi sui testi, gli algoritmi all'avanguardia o anche ingenui sono probabilmente ottimali. Miriamo 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 tengamos un modelo impreciso de los datos. El proyecto se centra en el diseño de algoritmos eficientes para el emparejamiento 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 aproximada de patrones bajo la distancia de Hamming y varios tipos de periodicidades aproximadas (cuasiperiodicidades) en los textos. Apuntamos a algoritmos eficientes en el peor de los casos; sin embargo, un estudio reciente en el área de la complejidad de grano fino sugiere que para algunos de los problemas en los textos, los algoritmos de vanguardia o incluso ingenuos son probablemente óptimos. También apuntamos a la verificación experimental de nuestros enfoques. (Spanish)
19 January 2022
0 references
I mønster matching, er det meget almindeligt, at input data er beskadiget, eller at vi kun har en upræcis model af dataene. Projektet fokuserer på design af effektive algoritmer til mønstermatchning og datastrukturer til indeksering af data med fejl og usikkerheder. Vores primære motivation er molekylærbiologi, hvor der anvendes flere modeller for usikre data: tekster med jokertegn, ubestemte tekster, vægtede sekvenser (dvs. positionsvægtmatricer) og profiler. Vi overvejer omtrentlige mønster matchning under Hamming afstand og forskellige former for omtrentlige hyppigheder (kvasiperiodiciteter) i tekster. Vi tilstræber i værste fald effektive algoritmer; den seneste undersøgelse inden for finkornet kompleksitet tyder imidlertid på, at for nogle af problemerne på teksterne er de nyeste eller endda naive algoritmer sandsynligvis optimale. Vi tilstræber også eksperimentel kontrol af vores tilgange. (Danish)
26 July 2022
0 references
Στην αντιστοίχιση προτύπων, είναι πολύ συνηθισμένο ότι τα δεδομένα εισόδου είναι κατεστραμμένα ή ότι έχουμε μόνο ένα ανακριβές μοντέλο των δεδομένων. Το έργο επικεντρώνεται στο σχεδιασμό αποτελεσματικών αλγορίθμων για την αντιστοίχιση προτύπων και δομών δεδομένων για την ευρετηρίαση δεδομένων με σφάλματα και αβεβαιότητες. Το κύριο κίνητρό μας είναι η μοριακή βιολογία, όπου χρησιμοποιούνται διάφορα μοντέλα για αβέβαια δεδομένα: κείμενα με μπαλαντέρ, απροσδιόριστα κείμενα, σταθμισμένες ακολουθίες (π.χ. πίνακες βάρους θέσης) και προφίλ. Εξετάζουμε την κατά προσέγγιση αντιστοίχιση μοτίβων κάτω από την απόσταση Hamming και διάφορα είδη κατά προσέγγιση περιοδικών (οιονεί περιοδικές) στα κείμενα. Στοχεύουμε σε χειρότερους αποδοτικούς αλγορίθμους. ωστόσο, πρόσφατη μελέτη στον τομέα της λεπτής πολυπλοκότητας δείχνει ότι για ορισμένα από τα προβλήματα στα κείμενα, οι υπερσύγχρονοι ή ακόμα και αφελείς αλγόριθμοι είναι πιθανώς βέλτιστοι. Επιδιώκουμε επίσης την πειραματική επαλήθευση των προσεγγίσεών μας. (Greek)
26 July 2022
0 references
U podudaranju uzoraka vrlo je često da su ulazni podaci oštećeni ili da imamo samo neprecizan model podataka. Projekt je usmjeren na osmišljavanje učinkovitih algoritama za uparivanje uzoraka i strukture 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 sa zamjenskim znakovima, neodređeni tekstovi, ponderirani slijedovi (tj. matrice za težinu položaja) i profili. Smatramo približni uzorak podudaranje pod Hamming udaljenost i razne vrste približne periodičnosti (kvaziperiodnosti) u tekstovima. Cilj nam je postići najučinkovitije algoritme; 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 frecvent ca datele de intrare să fie corupte sau că avem doar un model imprecis al datelor. Proiectul se concentrează pe proiectarea algoritmilor eficienți pentru corelarea modelelor și a structurilor de date pentru indexarea datelor cu erori și incertitudini. Motivația noastră principală este biologia moleculară, unde se folosesc mai multe modele de date incerte: texte cu wildcards, texte nedeterminate, secvențe ponderate (adică matrice de greutate a poziției) și profiluri. Luăm în considerare potrivirea aproximativă a modelelor sub distanța Hamming și diferitele tipuri de periodicități aproximative (cvasiperiodicități) în texte. Ne propunem algoritmi cei mai eficienți în cel mai rău caz; cu toate acestea, un studiu recent în domeniul complexității cu granulație fină sugerează că, pentru unele dintre problemele textelor, algoritmii de ultimă generație sau chiar naivi sunt, probabil, optimi. De asemenea, ne propunem verificarea experimentală a abordărilor noastre. (Romanian)
26 July 2022
0 references
Pri porovnávaní 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 zosúlaďovanie vzorov a dátových štruktúr na indexovanie údajov 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 s zástupnými znakmi, neurčitými textami, váženými sekvenciami (t. j. matricami hmotnosti pozície) a profilmi. Zvažujeme približnú zhodu vzoru pod vzdialenosťou Hammingu a rôzne druhy približných periodicít (kváziperiodicity) v textoch. Zameriavame sa na najhoršie efektívne algoritmy; nedávna štúdia v oblasti jemnozrnnej zložitosti však naznačuje, že pre niektoré problémy týkajúce sa textov sú pravdepodobne optimálne najmodernejšie alebo dokonca naivné algoritmy. Zameriavame sa aj na experimentálne overovanie našich prístupov. (Slovak)
26 July 2022
0 references
Fil tqabbil mudell, huwa komuni ħafna li d-data 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 tad-data bi żbalji u inċertezzi. 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 ppeżati (jiġifieri, matriċi tal-piż tal-pożizzjoni) u profili. Aħna nikkunsidraw it-tqabbil tal-mudell approssimattiv taħt id-distanza ta’ Hamming u diversi tipi ta’ perjodiċitajiet approssimattivi (kważiperjodiċitajiet) fit-testi. Aħna nimmiraw lejn algoritmi effiċjenti fl-agħar każ; madankollu, studju reċenti fil-qasam tal-kumplessità fina jissuġġerixxi li għal xi wħud mill-problemi fuq it-testi, l-algoritmi l-aktar avvanzati jew saħansitra dawk naive huma probabbilment ottimali. Għandna wkoll l-għan li nivverifikaw l-approċċi tagħna b’mod sperimentali. (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 vastaavuudessa on hyvin yleistä, että syöttötiedot ovat vioittuneita tai että meillä on vain epätarkka malli tiedoista. Hankkeessa keskitytään tehokkaiden algoritmien suunnitteluun kuvioiden täsmäyttämiseen ja tietorakenteisiin virheellisten ja epävarmojen tietojen indeksointia varten. Ensisijainen motivaatiomme on molekyylibiologia, jossa käytetään useita epävarmojen tietojen malleja: tekstit, joissa on jokerimerkkejä, määrittelemättömiä tekstejä, painotettuja sekvenssejä (ts. sijaintipainomatriiseja) ja profiileja. Tarkastelemme likimääräistä kuviota, joka vastaa Hamming-etäisyyttä ja erilaisia likimääräisiä jaksotuksia (kvasiperioditeetteja) teksteissä. Pyrimme pahimmassa tapauksessa tehokkaisiin algoritmeihin; äskettäinen tutkimus hienorakeisen monimutkaisuuden alalla viittaa kuitenkin siihen, että joidenkin tekstien ongelmien osalta huipputason tai jopa naiivin algoritmit ovat todennäköisesti optimaalisia. Pyrimme myös kokeilemaan lähestymistapojamme. (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 primarna motivacija je molekularna biologija, kjer se uporablja več modelov za negotove podatke: besedila z nadomestnimi znaki, nedoločena besedila, ponderirana zaporedja (tj. matrice za utež položaja) in profili. Upoštevamo približno ujemanje vzorcev pod Hammingovo razdaljo in različne vrste približnih periodičnosti (kvaziperiodnosti) v besedilih. Stremimo k najslabšim možnim učinkovitim algoritmom; vendar pa nedavna študija na področju drobnozrnate kompleksnosti kaže, da so za nekatere težave z besedili najsodobnejši ali celo naivni algoritmi verjetno optimalni. Prizadevamo si tudi za eksperimentalno preverjanje naših pristopov. (Slovenian)
26 July 2022
0 references
V souladu se vzorem 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 nejistotou. Naší primární motivací je molekulární biologie, kde se používá několik modelů pro nejistá data: texty s zástupnými znaky, neurčitými texty, váženými sekvencemi (tj. pozičními maticemi) a profily. Domníváme se, že přibližný vzor se shoduje pod Hammingovou vzdáleností a různé druhy přibližných periodicit (kvaziperiodicity) v textech. Zaměřujeme se na nejúčinnější algoritmy v nejhorším případě; nedávná studie v oblasti jemně zrnité složitosti však naznačuje, že pro některé problémy s texty jsou pravděpodobně optimální nejmodernější nebo dokonce naivní algoritmy. Zaměřujeme se také na experimentální ověření našich přístupů. (Czech)
26 July 2022
0 references
Modelio atitikimo atveju labai įprasta, kad įvesties duomenys yra sugadinti arba kad mes turime tik netikslų duomenų modelį. Projekte daugiausia dėmesio skiriama efektyvių modelių atitikimo algoritmų ir duomenų struktūrų, skirtų duomenų su klaidomis ir neapibrėžtumu indeksavimui, kūrimui. Mūsų pagrindinė motyvacija yra molekulinė biologija, kurioje naudojami keli neaiškių duomenų modeliai: tekstai su pakaitos kortomis, neapibrėžtais tekstais, svertinėmis sekomis (t. y. pozicijos svorio matricomis) ir profiliais. Mes manome, kad apytikslis modelis atitinka Hammingo atstumą ir įvairius apytikslius periodiškumą (kvaziperiodiškumą) tekstuose. Mes siekiame blogiausiu atveju efektyvių algoritmų; tačiau neseniai atliktas tyrimas smulkiojo grūdo sudėtingumo srityje rodo, kad kai kurioms tekstų problemoms greičiausiai optimalūs yra naujausi ar net naivūs algoritmai. Mes taip pat siekiame eksperimentinio mūsų metodų patikrinimo. (Lithuanian)
26 July 2022
0 references
Savietojot modeli, ir ļoti bieži, ka ievades dati ir bojāti vai ka mums ir tikai neprecīzs datu modelis. Projekta mērķis ir izstrādāt efektīvus algoritmus modeļu saskaņošanai un datu struktūras datu indeksēšanai ar kļūdām un neskaidrībā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 apsveram aptuveno modeli, kas atbilst Hamminga attālumam un dažāda veida aptuveno periodiskumu (kvaziperiodicities) tekstos. Mūsu mērķis ir vissliktākā gadījumā efektīvi algoritmi; tomēr nesenais pētījums smalko graudu sarežģītības jomā liecina, ka dažām problēmām saistībā ar tekstiem vismodernākie vai pat naivie 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 mintaegyeztetésben nagyon gyakori, hogy a bemeneti adatok sérültek, vagy hogy csak egy pontatlan adatmodellünk van. A projekt középpontjában a mintaegyeztetésre szolgáló hatékony algoritmusok, valamint a hibákkal és bizonytalanságokkal rendelkező adatok indexelésére szolgáló adatstruktúrák kialakítása áll. Elsődleges motivációnk a molekuláris biológia, ahol számos bizonytalan adatmodellt használnak: helyettesítő szövegek, meghatározatlan szövegek, súlyozott szekvenciák (azaz pozíciósúly mátrixok) és profilok. Figyelembe vesszük a közelítő minta egyezését a Hamming távolság és a különböző közelítő gyakoriságok (kváziperiodikák) szövegekben. Célunk a legrosszabb esetben hatékony algoritmusok kialakítása; a finomszemcsés komplexitásról szóló közelmúltbeli tanulmány azonban azt sugallja, hogy a szövegekkel kapcsolatos problémák egy része esetében a legkorszerűbb vagy akár naiv algoritmusok valószínűleg optimálisak. Célunk a megközelítéseink kísérleti ellenőrzése is. (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ú sonraí le haghaidh 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 oprecisa modell av data. Projektet fokuserar på utformning av effektiva algoritmer för mönstermatchning och datastrukturer för indexering av data med fel och osäkerhet. Vår primära motivation är molekylärbiologi, där flera modeller för osäkra data används: texter med jokertecken, obestämda texter, viktade sekvenser (dvs. positionsviktsmatriser) och profiler. Vi anser att ungefärlig mönstermatchning under Hamming-avståndet och olika typer av ungefärliga periodiciteter (kvasiperiodiciteter) i texter. Vi strävar efter värsta möjliga effektiva algoritmer. men ny studie inom området finkornig komplexitet tyder på att för några av problemen med texter är de senaste eller till och med naiva algoritmerna förmodligen optimala. Vi strävar också efter experimentell verifiering av våra tillvägagångssätt. (Swedish)
26 July 2022
0 references
Mustri sobitamisel on väga tavaline, et sisendandmed on rikutud või et meil on ainult andmete ebatäpne mudel. Projekt keskendub tõhusate algoritmide kavandamisele mustrite sobitamiseks ja andmestruktuuride väljatöötamiseks vigade ja ebakindlusega andmete indekseerimiseks. Meie peamine motivatsioon on molekulaarbioloogia, kus kasutatakse mitmeid ebakindlate andmete mudeleid: metakaartidega tekstid, määratlemata tekstid, kaalutud järjestused (st positsioonikaalu maatriksid) ja profiilid. Me kaalume ligikaudset mustri sobitamist vastavalt Hamming vahemaale ja erinevaid ligikaudseid perioode (kvaasiperioodilisus) tekstides. Meie eesmärgiks on halvimal juhul tõhusad algoritmid; kuid hiljutine uuring peeneteralise keerukuse valdkonnas näitab, et mõnede tekstidega seotud probleemide puhul on state-of-the-art 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
24 May 2023
0 references
Identifiers
POIR.04.04.00-00-24BA/16
0 references