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(n3) is presented.
Get full access to this article
View all access options for this article.
References
1.
GoldbergP.W., GolumbicM.C.et al.1995. Strikes against physical mapping of DNA. J. Comput. Biol., 2:139–152.
2.
GoldsteinL., WatermanM.S.1987. Mapping DNA by stochastic relaxation. Adv. Appl. Math., 8:194–207.
3.
GriggsJ.R., WatermanM.S.1986. Interval graphs and maps of DNA. Bull. Math. Biol., 48:189–195.
4.
LanderE.S., WatermanM.S.1988. Genomic mapping by fingerprinting random clones: a mathematical analysis. Genomics, 2:231–239.
5.
LekkerkerkerC.B., BolandJ.C.1962. Representation of a finite graph by a set of intervals on the real line. Fund. Math., 51:45–64.
6.
PevznerP.A., WatermanM.S.1995. Open combinatorial problems in computational molecular biology. Proc. 3rd Israel Symp. Theor. Comput. Syst.
7.
WangC.1994. A subgraph problem from restriction maps of DNA. J. Comput.Biol., 1:227–234.
