We describe some genome assembly problems as a general problem of covering a hypergraph by linear and circular walks, where vertices represent sequence elements, repeated sequences are modelled by assigning a multiplicity to vertices, and edges represent co-localization information. We show that deciding if a given assembly hypergraph ad- mits an assembly is fixed-parameter tractable, and we provide two exact polynomial time algorithms for clearing ambiguities caused by repeats.

Lecture Notes in Computer Science
International Workshop on Combinatorial Algorithms
Evolutionary Intelligence

Chauve, C., Patterson, M., & Rajaraman, A. (2013). Hypergraph covering problems motivated by genome assembly questions. In Lecture Notes in Computer Science (Vol. 8288). Springer. doi:10.1007/978-3-642-45278-9_37