Sequence-To-Graph Alignment (Sequence-to-Graph Alignment)
This is pattern matching where you are given a pattern and a hypertext graph. The hypertext model is that the text forms a graph of $N$ nodes and $E$ edges, where a string is stored inside each node, and the edges indicate alternative texts that may follow the current node. The pattern is still a simple string of length $m$. It is also customary to transform this graph into a one-character hypertext, i.e. one where there is exactly one character per node (by converting each node containing a text of length $l$ into a chain of $l$ nodes). This graph has $n$ nodes and $e$ edges (note that $n$ is the text size and $e = n − N + E$).
Additonal notes: (changes are allowed in the query sequence alone) Linear gap penalty?
$N$: number of vertices in original hypertext graph
$E$: number of edges in original hypertext graph
$m$: length of pattern
$n$: number of vertices in converted graph (total text size)
$e$: number of edges in converted graph
Table of Algorithms
Currently no algorithms in our database for the given problem.