×

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
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bodlaender, H. L.; de Fluiter, B., Intervalizing \(k\)-colored graphs, (Technical Report UU-CS-1995-15 (1995), Department of Computer Science, Utrecht University: Department of Computer Science, Utrecht University Utrecht) · Zbl 0867.92008
[2] Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Hallett, M. T.; Wareham, H. T., Parameterized complexity analysis in computational biology, Comput. Appl. Biosci., 11, 49-57 (1995)
[3] Bodlaender, H. L.; Fellows, M. R.; Hallett, M., Beyond NP-completeness for problems of bounded width: hardness for the \(W\) hierarchy, (Proceedings of the 26th Annual Symposium on Theory of Computing (1994), ACM Press: ACM Press New York), 449-458 · Zbl 1345.68152
[4] Bodlaender, H. L.; Fellows, M. R.; Warnow, T. J., Two strikes against perfect phylogeny, (Proceedings of the 19th International Colloquium on Automata, Languages and Programming. Proceedings of the 19th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 623 (1992), Springer: Springer Berlin), 273-283 · Zbl 1425.68136
[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), (Lengauer, T., Proceedings of the 1st Annual European Symposium on Algorithms ESA’93. Proceedings of the 1st Annual European Symposium on Algorithms ESA’93, Lecture Notes in Computer Science, Vol. 726 (1993), Springer: Springer Berlin), 157-168
[8] Garey, M. R.; Johnson, D. S., (Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York) · Zbl 0411.68039
[9] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: 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.; 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, (Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS) (1994), IEEE Computer Soc. Press: IEEE Computer Soc. Press Silver Spring, MD), 780-791
[16] Karp, R. M., Mapping the genome: some combinatorial problems arising in molecular biology, (Proceedings of the 25th Annual Symposium on Theory of Computing (1993), ACM Press: ACM Press New York), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.