×

zbMATH — the first resource for mathematics

On intervalizing \(k\)-colored graphs for DNA physical mapping. (English) Zbl 0867.92008
Summary: The problem of determining whether a given \(k\)-colored graph is a subgraph of a properly colored interval graph has an application in DNA physical mapping. We study the problem for the case that the number of colors \(k\) is fixed. For \(k=2\), we give a simple linear time algorithm, for \(k=3\), we give an \(O(n^2)\) algorithm for biconnected graphs with \(n\) vertices, and for \(k=4\), we show that the problem is NP-complete.

MSC:
92C40 Biochemistry, molecular biology
92D20 Protein sequences, DNA sequences
05C90 Applications of graph theory
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Bodlaender, H.L.; de Fluiter, B., Intervalizing k-colored graphs, () · Zbl 0867.92008
[2] extended abstract in: Procedings ICALP’95.
[3] Bodlaender, H.L.; Fellows, M.R.; Hallett, M., Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy, (), 449-458 · Zbl 1345.68152
[4] Bodlaender, H.L.; Fellows, M.R.; Warnow, T.J., Two strikes against perfect phylogeny, (), 273-283
[5] Bodlaender, H.L.; Kloks, T., A simple linear time algorithm for triangulating three-colored graphs, J. algorithms, 15, 160-172, (1993) · Zbl 0785.68042
[6] Bodlaender, H.L.; Möhring, R.H., The pathwidth and treewidth of cographs, SIAM J. discrete math., 6, 181-188, (1993) · Zbl 0773.05091
[7] Fellows, M.R.; Hallett, M.T.; Wareham, H.T., DNA physical mapping: three ways difficult (extended abstract), (), 157-168
[8] Garey, M.R.; Johnson, D.S., ()
[9] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[10] Golumbic, M.C.; Kaplan, H.; Shamir, R., On the complexity of DNA physical mapping, Adv. appl. math., 15, 251-261, (1994) · Zbl 0806.92007
[11] Idury, R.; Schaffer, A., Triangulating three-colored graphs in linear time and linear space, SIAM J. discrete math., 2, 289-293, (1993) · Zbl 0798.68127
[12] Jungck, J.R.; Dick, G.; Dick, A.G., Computer-assisted sequencing, interval graphs, and molecular evolution, Biosystems, 15, 259-273, (1982)
[13] Kannan, S.; Warnow, T., Triangulating 3-colored graphs, SIAM J. discrete math., 5, 249-258, (1992) · Zbl 0779.05020
[14] SIAM J. Comput., to appear. · Zbl 0852.68072
[15] Kaplan, H.; Shamir, R.; Tarjan, R.E., Tractability of parameterized completion problems on chordal and interval graphs: minimum fill-in and physical mapping, (), 780-791
[16] Karp, R.M., Mapping the genome: some combinatorial problems arising in molecular biology, (), 278-285 · Zbl 1310.92022
[17] McMorris, F.R.; Warnow, T.; Wimer, T., Triangulating vertex-colored graphs, SIAM J. discrete math., 7, 296-306, (1994) · Zbl 0796.05087
[18] Nakano, S.-L.; Oguma, T.; Nishizeki, T., A linear time algorithm for c-triangulating three-colored graphs, Trans. ins. electron. inform. commun. eng. A, 377-A, 543-546, (1994), (in Japanese)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.