Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 8288))
Included in the following conference series:
913Accesses
Abstract
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 admits an assembly is fixed-parameter tractable, and we provide two exact polynomial time algorithms for clearing ambiguities caused by repeats.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Batzoglou, S., Istrail, S.: Physical mapping with repeated probes: The hypergraph superstring problem. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol. 1645, pp. 66–77. Springer, Heidelberg (1999)
Chauve, C., Maňuch, J., Patterson, M., Wittler, R.: Tractability results for the consecutive-ones property with multiplicity. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 90–103. Springer, Heidelberg (2011)
Chauve, C., Patterson, M., Rajaraman, A.: Hypergraph covering problems motivated by genome assembly questions. arXiv:1306.4353 [cs.DS] (2013)
Dom, M.: Algorithimic aspects of the consecutive-ones property. Bull. EATCS 98, 27–59 (2009)
Manuch, J., Patterson, M., Wittler, R., Chauve, C., Tannier, E.: Linearization of ancestral multichromosomal genomes. BMC Bioinformatics 13(suppl. 19), S11 (2012)
Wittler, R., Manuch, J., Patterson, M., Stoye, J.: Consistency of sequence-based gene clusters. J. Comput. Biol. 18, 1023–1039 (2011)
Author information
Authors and Affiliations
LaBRI, Université Bordeaux 1, Bordeaux, France
Cedric Chauve
Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada
Cedric Chauve & Ashok Rajaraman
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands
Murray Patterson
International Graduate Training Center in Mathematical Biology, PIMS, Canada
Ashok Rajaraman
- Cedric Chauve
You can also search for this author inPubMed Google Scholar
- Murray Patterson
You can also search for this author inPubMed Google Scholar
- Ashok Rajaraman
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
UFR des Sciences et Techniques, LITIS, Université de Rouen, 76821, EA 4180, Mont Saint Aignan Cedex, France
Thierry Lecroq & Laurent Mouchard &
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chauve, C., Patterson, M., Rajaraman, A. (2013). Hypergraph Covering Problems Motivated by Genome Assembly Questions. In: Lecroq, T., Mouchard, L. (eds) Combinatorial Algorithms. IWOCA 2013. Lecture Notes in Computer Science, vol 8288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45278-9_37
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-45277-2
Online ISBN:978-3-642-45278-9
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative