Sequence-To-Graph Alignment

Description

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?

Parameters

$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.