Zhang Haiying, Zhou Bing
Department of Mathematics, Trent University, Peterborough, Canada.
J Comput Biol. 2010 Oct;17(10):1425-33. doi: 10.1089/cmb.2009.0039.
We study the problem of finding the maximum interval subgraph in a tree. This problem is related to the Double Digestion Problem of DNA physical mapping. We show that the complexity of an algorithm of Wang is O(n). We also present a linear algorithm of our own. We study the case when the edges of the tree is weighted as well. An algorithm with complexity O(n³) is presented.
我们研究在一棵树中寻找最大区间子图的问题。这个问题与DNA物理图谱的双酶切问题相关。我们证明了Wang的一个算法的复杂度为O(n)。我们还给出了一个我们自己的线性算法。我们也研究了树的边带权的情况。给出了一个复杂度为O(n³)的算法。
