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.

Additional Metadata
THEME Life Sciences (theme 5)
Publisher Springer
Persistent URL dx.doi.org/10.1007/978-3-642-45278-9_37
Journal Lecture Notes in Computer Science
Conference International Workshop on Combinatorial Algorithms
Citation
Chauve, C, Patterson, M.D, & 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