一个来自DNA限制图谱的子图问题。

A subgraph problem from restriction maps of DNA.

作者信息

Wang C

机构信息

Department of Mathematics, University of Louisville, KY 40292, USA.

出版信息

J Comput Biol. 1994 Fall;1(3):227-34. doi: 10.1089/cmb.1994.1.227.

DOI:10.1089/cmb.1994.1.227

PMID:8790467

Abstract

Computing the minimum number of edge removals needed to convert a bipartite graph into an interval graph was proposed by Waterman and Griggs in the study of restriction maps of DNA. We show that this problem is N P-complete and we give a polynomial algorithm that finds an edge-maximum interval subgraph for trees. Then various heuristics can be devised using this algorithm.

摘要

沃特曼和格里格斯在对DNA限制图谱的研究中提出了计算将二分图转换为区间图所需移除的最少边数的问题。我们证明了这个问题是NP完全问题，并给出了一种多项式算法，该算法能找到树的边最大区间子图。然后可以使用该算法设计各种启发式算法。