Abstract
The paired de Bruijn graph is an extension of de Bruijn graph incorporating mate pair information for genome assembly proposed by Mevdedev et al. However, unlike in an ordinary de Bruijn graph, not every path or cycle in a paired de Bruijn graph will spell a string, because there is an additional soundness constraint on the path. In this paper we show that the problem of checking if there is a sound cycle in a paired de Bruijn graph is NP-hard in general case. We also explore some of its special cases, as well as a modified version where the cycle must also pass through every edge.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Galant, J., Maier, D., Astorer, J.: On finding minimal length superstrings. Journal of Computer and System Sciences 20(1), 50–58 (1980)
Kapun, E., Tsarev, F.: De Bruijn superwalk with multiplicities problem is NP-hard. BMC Bioinformatics 14(suppl. 5), S7 (2013)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computation. The IBM Research Symposia Series, pp. 85–103. Plenum Press (1972)
Mahaney, S.R.: Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences 25(2), 130–143 (1982)
Medvedev, P., Brudno, M.: Maximum likelihood genome assembly. Journal of Computational Biology 16(8), 1101–1116 (2009)
Medvedev, P., Georgiou, K., Myers, G., Brudno, M.: Computability of models for sequence assembly. In: Giancarlo, R., Hannenhalli, S. (eds.) WABI 2007. LNCS (LNBI), vol. 4645, pp. 289–301. Springer, Heidelberg (2007)
Medvedev, P., Pham, S., Chaisson, M., Tesler, G., Pevzner, P.: Paired de Bruijn graphs: A novel approach for incorporating mate pair information into genome assemblers. Journal of Computational Biology 18(11), 1625–1634 (2011)
Pevzner, P.A., Tang, H., Waterman, M.S.: An eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences 98(17), 9748–9753 (2001)
Pham, S.: Mate-pair consistency and generating problems. In: Talk at RECOMB Satellite Conference on Open Problems in Algorithmic Biology (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kapun, E., Tsarev, F. (2013). On NP-Hardness of the Paired de Bruijn Sound Cycle Problem. In: Darling, A., Stoye, J. (eds) Algorithms in Bioinformatics. WABI 2013. Lecture Notes in Computer Science(), vol 8126. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40453-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-40453-5_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40452-8
Online ISBN: 978-3-642-40453-5
eBook Packages: Computer ScienceComputer Science (R0)