title: Reconstruction of viral population structure from next-generation sequencing data using multicommodity flows.
abstract: BACKGROUND
  Highly mutable RNA viruses exist in infected hosts as heterogeneous populations of genetically close variants known as quasispecies. Next-generation sequencing (NGS) allows for analysing a large number of viral sequences from infected patients, presenting a novel opportunity for studying the structure of a viral population and understanding virus evolution, drug resistance and immune escape. Accurate reconstruction of genetic composition of intra-host viral populations involves assembling the NGS short reads into whole-genome sequences and estimating frequencies of individual viral variants. Although a few approaches were developed for this task, accurate reconstruction of quasispecies populations remains greatly unresolved.
  
  
  RESULTS
  Two new methods, AmpMCF and ShotMCF, for reconstruction of the whole-genome intra-host viral variants and estimation of their frequencies were developed, based on Multicommodity Flows (MCFs). AmpMCF was designed for NGS reads obtained from individual PCR amplicons and ShotMCF for NGS shotgun reads. While AmpMCF, based on covering formulation, identifies a minimal set of quasispecies explaining all observed reads, ShotMCS, based on packing formulation, engages the maximal number of reads to generate the most probable set of quasispecies. Both methods were evaluated on simulated data in comparison to Maximum Bandwidth and ViSpA, previously developed state-of-the-art algorithms for estimating quasispecies spectra from the NGS amplicon and shotgun reads, respectively. Both algorithms were accurate in estimation of quasispecies frequencies, especially from large datasets.
  
  
  CONCLUSIONS
  The problem of viral population reconstruction from amplicon or shotgun NGS reads was solved using the MCF formulation. The two methods, ShotMCF and AmpMCF, developed here afford accurate reconstruction of the structure of intra-host viral population from NGS reads. The implementations of the algorithms are available at http://alan.cs.gsu.edu/vira.html (AmpMCF) and http://alan.cs.gsu.edu/NGS/?q=content/shotmcf (ShotMCF).
authors.affiliation: Laboratory of Molecular Epidemiology and Bioinformatics, Division of Viral Hepatitis, Centers for Disease Control and Prevention, 1600 Clifton Road NE, 30333 Atlanta, GA, USA. kki8@cdc.gov
authors.forename: Pavel
authors.initials: P
authors.lastname: Skums
authors.forename: Nicholas
authors.initials: N
authors.lastname: Mancuso
authors.forename: Alexander
authors.initials: A
authors.lastname: Artyomenko
authors.forename: Bassam
authors.initials: B
authors.lastname: Tork
authors.forename: Ion
authors.initials: I
authors.lastname: Mandoiu
authors.forename: Yury
authors.initials: Y
authors.lastname: Khudyakov
authors.forename: Alex
authors.initials: A
authors.lastname: Zelikovsky
mesh_terms: D000465:Algorithms; D014644:Genetic Variation; D016679:Genome, Viral; D016174:Hepacivirus / Q000145:classification / Q000235:genetics; D012328:RNA Viruses / Q000145:classification / Q000235:genetics*; D017423:Sequence Analysis, RNA / Q000379:methods*
references.citation: BMC Bioinformatics. 2011;12 Suppl 6:S1
references.pmid: 21989211
references.citation: BMC Bioinformatics. 2011 Jan 05;12:5
references.pmid: 21208435
references.citation: Bioinformatics. 2010 Sep 15;26(18):i420-5
references.pmid: 20823302
references.citation: PLoS Comput Biol. 2008 May 09;4(4):e1000074
references.pmid: 18437230
references.citation: Gastroenterology. 2007 Feb;132(2):667-78
references.pmid: 17258731
references.citation: BMC Bioinformatics. 2011 Jan 28;12:38
references.pmid: 21276213
references.citation: BMC Bioinformatics. 2012 Jun 25;13 Suppl 10:S6
references.pmid: 22759430
references.citation: In Silico Biol. 2011-2012;11(5-6):263-9
references.pmid: 23202427
references.citation: Front Microbiol. 2012 Sep 11;3:329
references.pmid: 22973268
references.citation: Curr Opin Virol. 2011 Nov;1(5):413-8
references.pmid: 22440844
references.citation: Infect Agents Dis. 1994 Aug;3(4):201-14
references.pmid: 7827789
references.citation: In Silico Biol. 2011-2012;11(5-6):237-49
references.pmid: 23202425
references.citation: Trends Biotechnol. 2012 Sep;30(9):443-52
references.pmid: 22721705
references.citation: BMC Bioinformatics. 2011 Apr 26;12:119
references.pmid: 21521499