title: Building a pan-genome reference for a population.
abstract: A reference genome is a high quality individual genome that is used as a coordinate system for the genomes of a population, or genomes of closely related subspecies. Given a set of genomes partitioned by homology into alignment blocks we formalize the problem of ordering and orienting the blocks such that the resulting ordering maximally agrees with the underlying genomes' ordering and orientation, creating a pan-genome reference ordering. We show this problem is NP-hard, but also demonstrate, empirically and within simulations, the performance of heuristic algorithms based upon a cactus graph decomposition to find locally maximal solutions. We describe an extension of our Cactus software to create a pan-genome reference for whole genome alignments, and demonstrate how it can be used to create novel genome browser visualizations using human variation data as a test. In addition, we test the use of a pan-genome for describing variations and as a reference for read mapping.
authors.affiliation: 1 Center for Biomolecular Science and Engineering, University of California , Santa Cruz, California.
authors.forename: Ngan
authors.initials: N
authors.lastname: Nguyen
authors.forename: Glenn
authors.initials: G
authors.lastname: Hickey
authors.forename: Daniel R
authors.initials: DR
authors.lastname: Zerbino
authors.forename: Brian
authors.initials: B
authors.lastname: Raney
authors.forename: Dent
authors.initials: D
authors.lastname: Earl
authors.forename: Joel
authors.initials: J
authors.lastname: Armstrong
authors.forename: W James
authors.initials: WJ
authors.lastname: Kent
authors.forename: David
authors.initials: D
authors.lastname: Haussler
authors.forename: Benedict
authors.initials: B
authors.lastname: Paten
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D019143:Evolution, Molecular; D005828:Genetics, Population / Q000592:standards* / Q000706:statistics & numerical data; D015894:Genome, Human; D006801:Humans; D012015:Reference Standards; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D012984:Software
keywords: algorithms; computational molecular biology; genomics; molecular evolution; sequence analysis