Hypergraph covering problems motivated by genome assembly questions
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.
|THEME||Life Sciences (theme 5)|
|Journal||Lecture Notes in Computer Science|
|Conference||International Workshop on Combinatorial Algorithms|
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