2013
Hypergraph covering problems motivated by genome assembly questions
Publication
Publication
Lecture Notes in Computer Science , Volume 8288
Presented at the
International Workshop on Combinatorial Algorithms, Rouen, France
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 | |
|---|---|
| Springer | |
| doi.org/10.1007/978-3-642-45278-9_37 | |
| Lecture Notes in Computer Science | |
| International Workshop on Combinatorial Algorithms | |
| Organisation | 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 |
|