Mako: A Graph-based Pattern Growth Approach to Detect Complex Structural Variants

Jiadong Lin; Xiaofei Yang; Walter Kosters; Tun Xu; Yanyan Jia; Songbo Wang; Qihui Zhu; Mallory Ryan; Li Guo; Chengsheng Zhang; Human Genome Structural Variation Consortium; Charles Lee; Scott E Devine; Evan E Eichler; Kai Ye

doi:10.1016/j.gpb.2021.03.007

Mako: A Graph-based Pattern Growth Approach to Detect Complex Structural Variants

Genomics Proteomics Bioinformatics. 2022 Feb;20(1):205-218. doi: 10.1016/j.gpb.2021.03.007. Epub 2021 Jul 3.

Authors

Jiadong Lin¹, Xiaofei Yang², Walter Kosters³, Tun Xu⁴, Yanyan Jia⁴, Songbo Wang⁴, Qihui Zhu⁵, Mallory Ryan⁵, Li Guo⁶, Chengsheng Zhang⁷; Human Genome Structural Variation Consortium; Charles Lee⁷, Scott E Devine²⁴, Evan E Eichler²⁵, Kai Ye²⁶

Collaborators

Human Genome Structural Variation Consortium:
Mark B Gerstein⁸, Ashley D Sanders⁹, Micheal C Zody¹⁰, Michael E Talkowski¹¹, Ryan E Mills¹², Jan O Korbel⁹, Tobias Marschall¹³, Peter Ebert¹³, Peter A Audano¹⁴, Bernardo Rodriguez-Martin⁹, David Porubsky¹³, Marc Jan Bonder¹⁵, Arvis Sulovari¹⁴, Jana Ebler¹³, Weichen Zhou¹², Rebecca Serra Mari¹³, Feyza Yilmaz¹⁶, Xuefang Zhao¹¹, PingHsun Hsieh¹⁴, Joyce Lee¹⁷, Sushant Kumar⁸, Tobias Rausch⁹, Yu Chen¹⁸, Zechen Chong¹⁸, Katherine M Munson¹⁴, Mark J P Chaisson¹⁹, Junjie Chen²⁰, Xinghua Shi²⁰, Aaron M Wenger²¹, William T Harvey¹⁴, Patrick Hansenfeld⁹, Allison Regier²², Ira M Hall²², Paul Flicek²³, Alex R Hastie¹⁷, Susan Fairely²³

Affiliations

¹ School of Automation Science and Engineering, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China; MOE Key Lab for Intelligent Networks & Networks Security, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China; Genome Institute, the First Affiliated Hospital of Xi'an Jiaotong University, Xi'an 710061, China; Leiden Institute of Advanced Computer Science, Faculty of Science, Leiden University, Leiden 2311EZ, Netherland.
² MOE Key Lab for Intelligent Networks & Networks Security, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China; School of Computer Science and Technology, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China.
³ Leiden Institute of Advanced Computer Science, Faculty of Science, Leiden University, Leiden 2311EZ, Netherland.
⁴ School of Automation Science and Engineering, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China.
⁵ The Jackson Laboratory for Genomic Medicine, Farmington, CT 06032, USA.
⁶ MOE Key Lab for Intelligent Networks & Networks Security, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China.
⁷ The Jackson Laboratory for Genomic Medicine, Farmington, CT 06032, USA; Precision Medicine Center, the First Affiliated Hospital of Xi'an Jiaotong University, Xi'an 710061, China.
⁸ Program in Computational Biology and Bioinformatics, Yale University, New Haven, CT 06520, USA.
⁹ European Molecular Biology Laboratory (EMBL), Genome Biology Unit, D-69117 Heidelberg, Germany.
¹⁰ New York Genome Center, New York, NY 10013, USA.
¹¹ Center for Genomic Medicine, Massachusetts General Hospital, Department of Neurology, Harvard Medical School, Boston, MA 02114, USA.
¹² Department of Computational Medicine & Bioinformatics, University of Michigan, Ann Arbor, MI 48109, USA.
¹³ Heinrich Heine University, Medical Faculty, Institute for Medical Biometry and Bioinformatics, D-40225 Düsseldorf, Germany.
¹⁴ Department of Genome Sciences, University of Washington School of Medicine, Seattle, WA 98195-5065, USA.
¹⁵ European Molecular Biology Laboratory (EMBL), Genome Biology Unit, D-69117 Heidelberg, Germany; Division of Computational Genomics and Systems Genetics, German Cancer Research Center (DKFZ), D-69120 Heidelberg, Germany.
¹⁶ The Jackson Laboratory for Genomic Medicine, Farmington, CT 06030, USA.
¹⁷ Bionano Genomics, San Diego, CA 92121, USA.
¹⁸ Department of Genetics and Informatics Institute, School of Medicine, University of Alabama at Birmingham, Birmingham, AL 35294, USA.
¹⁹ Molecular and Computational Biology, University of Southern California, Los Angeles, CA 90089, USA.
²⁰ Department of Computer & Information Sciences, Temple University, Philadelphia, PA 19122, USA.
²¹ Pacific Biosystems of California, Inc, Menlo Park, CA 94025, USA.
²² Washington University, St. Louis, MO 63108, USA.
²³ European Molecular Biology Laboratory, European Bioinformatics Institute, Wellcome Genome Campus, Hinxton, Cambridge, CB10 1SD, United Kingdom.
²⁴ School of Automation Science and Engineering, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China; Institute for Genome Sciences, University of Maryland School of Medicine, Baltimore, MD 21201, USA.
²⁵ Department of Genome Sciences, University of Washington School of Medicine, Seattle, WA 98119, USA; Howard Hughes Medical Institute, University of Washington, Seattle, WA 98195, USA.
²⁶ School of Automation Science and Engineering, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China; MOE Key Lab for Intelligent Networks & Networks Security, Faculty of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China; Genome Institute, the First Affiliated Hospital of Xi'an Jiaotong University, Xi'an 710061, China; The School of Life Science and Technology, Xi'an Jiaotong University, Xi'an 710049, China. Electronic address: kaiye@xjtu.edu.cn.

Abstract

Complex structural variants (CSVs) are genomic alterations that have more than two breakpoints and are considered as the simultaneous occurrence of simple structural variants. However, detecting the compounded mutational signals of CSVs is challenging through a commonly used model-match strategy. As a result, there has been limited progress for CSV discovery compared with simple structural variants. Here, we systematically analyzed the multi-breakpoint connection feature of CSVs, and proposed Mako, utilizing a bottom-up guided model-free strategy, to detect CSVs from paired-end short-read sequencing. Specifically, we implemented a graph-based pattern growth approach, where the graph depicts potential breakpoint connections, and pattern growth enables CSV detection without pre-defined models. Comprehensive evaluations on both simulated and real datasets revealed that Mako outperformed other algorithms. Notably, validation rates of CSVs on real data based on experimental and computational validations as well as manual inspections are around 70%, where the medians of experimental and computational breakpoint shift are 13 bp and 26 bp, respectively. Moreover, the Mako CSV subgraph effectively characterized the breakpoint connections of a CSV event and uncovered a total of 15 CSV types, including two novel types of adjacent segment swap and tandem dispersed duplication. Further analysis of these CSVs also revealed the impact of sequence homology on the formation of CSVs. Mako is publicly available at https://github.com/xjtu-omics/Mako.

Keywords: Complex structural variant; Formation mechanism; Graph mining; Next-generation sequencing; Pattern growth.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Genome
Genomics*
High-Throughput Nucleotide Sequencing
Mutation
Sequence Analysis, DNA

Abstract

Publication types

MeSH terms

Grants and funding