Browsing by Subject "flow networks"

The problem of safety in a general graph is the problem of finding walks in the graph that are subwalks of a walk in any possible solution within a given model (Tomescu and Medvedev, 2017). The problem of safety has proven to be a valuable problem for bioinformatics in the context of genome assembly and other assembly problems. When working with perfect data, safe walks in a graph correspond to correct sequences of the genome. When working with real (erroneous) data, safe walks correspond to close to correct sequences, where the errors correspond only to errors already in the data. Safety has previously been considered in two different models: in a model where the graph holds only the information of graph topology, and in a model where the graph holds the information of graph topology and network flow. Subpath constraints are paths in a graph that restrict the solution set. Restricting a solution set increases the lengths of safe walks, so using a model that holds the information of subpath constraints is advantageous. However, subpath constraints have never been considered with the problem of safety. In this work, we introduce subwalk constraints, which are subpath constraints that can have cycles and are not limited to directed acyclic graphs (DAGs). Then, we present a new model, where the graph holds the information of graph topology, network flow and subwalk constraints. In the new model, we present three methodologies to compute safe walks that become possible because of subwalk constraints. Then, we present an algorithm that computes safe walks in polynomial time in the new model utilizing the three new methodologies. Due to the new model, all safe walks produced by other algorithms are subwalks of the safe walks generated by our new algorithm