Safety of Flow Decompositions in DAGs
Safety of Flow Decompositions in DAGs
复制标题
DAG 中流分解的安全性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Alexandru I. Tomescu
中科院分区：
文献类型：
--
作者：
Shahbaz Khan;Alexandru I. Tomescu
网络流是一个研究最多的组合优化问题，有着无数的应用。有向无环图（DAG）上的任意流都可以分解为一组O（m）路径，其应用范围从网络路由到生物序列的组装。在一些应用中，流分解对应于需要从流重构的一些特定数据，这需要找到出现在所有可能的流分解中的路径（或子路径），称为安全路径。
最近，Ma等人[WABI 2020]在概率框架中解决了一个相关问题。后来，他们给出了一个基于全局准则的二次时间算法，用于相应问题的广义版本（AND-Quant），即，报告给定的流动路径是否安全。我们的贡献如下：
1-基于局部准则对给定路径的安全性进行了简单的刻画，可直接用于给出最优的线性时间验证算法。
2-一个简单的枚举算法，在$O（mn）$时间内报告流网络上的所有最大安全路径。该算法使用解的紧凑表示（称为${cal P}_c$）报告所有安全路径，在最坏情况下为$Omega（mn）$，但在最好情况下仅为$O（m+n）$。
3-一个改进的枚举算法，其中所有结束于每个顶点的安全路径都表示为漏斗，使用$O（n^2+|{cal P}_c|）$ space。这些可以计算并用于报告所有最大安全路径，使用漏斗所需的总空间中的时间线性，并具有额外的对数因子。
总的来说，我们提出了一个简单的问题，导致一个最佳的验证算法和一个简单的枚举算法表征。对枚举算法进行了改进，使用漏斗结构来寻找可能独立感兴趣的安全路径。
Network flows are one of the most studied combinatorial optimization problems with innumerable applications. Any flow on a directed acyclic graph (DAG) $G$ having $n$ vertices and $m$ edges can be decomposed into a set of $O(m)$ paths, with applications from network routing to assembly of biological sequences. In some applications, the flow decomposition corresponds to some particular data that need to be reconstructed from the flow, which require finding paths (or subpaths) appearing in all possible flow decompositions, referred to as safe paths.
Recently, Ma et al. [WABI 2020] addressed a related problem in a probabilistic framework. Later, they gave a quadratic-time algorithm based on a global criterion, for a generalized version (AND-Quant) of the corresponding problem, i.e., reporting if a given flow path is safe. Our contributions are as follows:
1- A simple characterization for the safety of a given path based on a local criterion, which can be directly adapted to give an optimal linear time verification algorithm.
2- A simple enumeration algorithm that reports all maximal safe paths on a flow network in $O(mn)$ time. The algorithm reports all safe paths using a compact representation of the solution (called ${cal P}_c$), which is $Omega(mn)$ in the worst case, but merely $O(m+n)$ in the best case.
3- An improved enumeration algorithm where all safe paths ending at every vertex are represented as funnels using $O(n^2+|{cal P}_c|)$ space. These can be computed and used to report all maximal safe paths, using time linear in the total space required by funnels, with an extra logarithmic factor.
Overall we present a simple characterization for the problem leading to an optimal verification algorithm and a simple enumeration algorithm. The enumeration algorithm is improved using the funnel structures for safe paths, which may be of independent interest.
使用不精确流程的 RNA 转录本组装
DOI：
10.1109/bibm47256.2019.8983180
发表时间：
2019
期刊：
2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM
影响因子：
--
作者：
Williams, Lucia;Reynolds, Gillian;Mumey, Brendan
通讯作者：
Mumey, Brendan