Aiming to foster future collaborations between researchers in algorithms, bioinformatics, and molecular biology, this book serves as an up-to-date survey of the most important recent developments and computational challenges in various application areas of next-generation sequencing technologies. Offering helpful insight from renowned experts, the book covers topics such as NGS error correction, road mapping, variant detection and genotyping, characterization of structural variants with NGS, genome-assisted transcriptome reconstruction, small RNA analysis, and much more.

Ion Mandoiu, PhD, is an associate professor in the Computer Science and Engineering Department at the University of Connecticut, USA. His main research interests are in the design and analysis of approximation algorithms for NP-hard optimization problems, particularly in the area of bioinformatics. Dr. Mandoiu has authored over 100 refereed articles in journals and conference proceedings. He has also co-edited (with A. Zelikovsky) a book on Bioinformatics Algorithms: Techniques and Applications (Wiley 2008).

Alexander Zelikovsky, PhD, is a Distinguished University Professor with the Computer Science Department at the Georgia State University, USA. His research focuses on discrete algorithms and their applications in computational biotechnology and biology, bioinformatics, VLSI CAD, and wireless networks. Dr. Zelikovsky has authored more than 170 refereed publications. He served as the co-Chair of International Symposium on Bioinformatics Research and Applications (2005-2016) and the Workshop on Computational Advances in Next-Generation Sequencing (2011-2015).

CONTRIBUTORS xix

PREFACE xxiii

ABOUT THE COMPANION WEBSITE xxv

PART I COMPUTING AND EXPERIMENTAL INFRASTRUCTURE FOR NGS 1

1 Cloud Computing for Next-Generation Sequencing Data Analysis 3
Xuan Guo, Ning Yu, Bing Li, and Yi Pan

2 Introduction to the Analysis of Environmental Sequence Information Using Metapathways 25
Niels W. Hanson, Kishori M. Konwar, Shang-Ju Wu, and Steven J. Hallam

3 Pooling Strategy for Massive Viral Sequencing 57
Pavel Skums, Alexander Artyomenko, Olga Glebova, Sumathi Ramachandran, David S. Campo, Zoya Dimitrova, Ion I. Mândoiu, Alexander Zelikovsky, and Yury Khudyakov

4 Applications of High-Fidelity Sequencing Protocol to RNA Viruses 85
Serghei Mangul, Nicholas C. Wu, Ekaterina Nenastyeva, Nicholas Mancuso, Alexander Zelikovsky, Ren Sun, and Eleazar Eskin

PART II GENOMICS AND EPIGENOMICS 105

5 Scaffolding Algorithms 107
Igor Mandric, James Lindsay, Ion I.Mândoiu, and Alexander Zelikovsky

6 Genomic Variants Detection and Genotyping 133
Jorge Duitama

7 Discovering and Genotyping Twilight Zone Deletions 149
Tobias Marschall and Alexander Schönhuth

8 Computational Approaches for Finding Long Insertions and Deletions with NGS Data 175
Jin Zhang, Chong Chu, and Yufeng Wu

9 Computational Approaches in Next-Generation Sequencing Data Analysis for Genome-Wide DNA Methylation Studies 197
Jeong-Hyeon Choi and Huidong Shi

10 Bisulfite-Conversion-Based Methods for DNA Methylation Sequencing Data Analysis 227
Elena Harris and Stefano Lonardi

PART III TRANSCRIPTOMICS 245

11 Computational Methods for Transcript Assembly from RNA-SEQ Reads 247
Stefan Canzar and Liliana Florea

12 An Overview And Comparison of Tools for RNA-Seq Assembly 269
Rasiah Loganantharaj and Thomas A. Randall

13 Computational Approaches for Studying Alternative Splicing in Nonmodel Organisms From RNA-SEQ Data 287
Sing-Hoi Sze

14 Transcriptome Quantification and Differential Expression From NGS Data 301
Olga Glebova, Yvette Temate-Tiagueu, Adrian Caciula, Sahar Al Seesi, Alexander Artyomenko, Serghei Mangul, James Lindsay, Ion I. M¢andoiu, and Alexander Zelikovsky

PART IV MICROBIOMICS 329

15 Error Correction of NGS Reads from Viral Populations 331
Pavel Skums, Alexander Artyomenko, Olga Glebova, David S. Campo, Zoya Dimitrova, Alexander Zelikovsky, and Yury Khudyakov

16 Probabilistic Viral Quasispecies Assembly 355
Armin Töpfer and Niko Beerenwinkel

17 Reconstruction of Infectious Bronchitis Virus Quasispecies from NGS Data 383
Bassam Tork, Ekaterina Nenastyeva, Alexander Artyomenko, Nicholas Mancuso, Mazhar I. Khan, Rachel O’Neill, Ion I. Mândoiu, and Alexander Zelikovsky

18 Microbiome Analysis: State of the Art and Future Trends 401
Mitch Fernandez, Vanessa Aguiar-Pulido, Juan Riveros, Wenrui Huang, Jonathan Segal, Erliang Zeng, Michael Campos, Kalai Mathee, and Giri Narasimhan

INDEX 425