%42%69%6f%69%6e%66%6f%72%6d%61%74%69%63%73
-
Machine Learning-Based Algorithm to Speed up DNA Sequencing
The algorithm presents the first full-fledged, short-read alignment software that leverages learned indices for solving the exact match search problem for efficient seeding
The human genome consists of a complete set of DNA, which is about 6.4 billion letters long. Because of its size, reading the whole genome sequence at once is challenging. So scientists use DNA sequencers to produce hundreds of millions of DNA sequence fragments, or short reads, up to 300 letters long. Then the DNA sequencer assembles all the short reads like a giant jigsaw puzzle to reconstruct the entire genome sequence. Even with very fast computers, this job can take hours to complete.
A research team at KAIST has achieved up to 3.45x faster speeds by developing the first short-read alignment software that uses a recent advance in machine-learning called a learned index.
The research team reported their findings on March 7, 2022 in the journal Bioinformatics. The software has been released as open source and can be found on github (https://github.com/kaist-ina/BWA-MEME).
Next-generation sequencing (NGS) is a state-of-the-art DNA sequencing method. Projects are underway with the goal of producing genome sequencing at population scale. Modern NGS hardware is capable of generating billions of short reads in a single run. Then the short reads have to be aligned with the reference DNA sequence. With large-scale DNA sequencing operations running hundreds of next-generation sequences, the need for an efficient short read alignment tool has become even more critical. Accelerating the DNA sequence alignment would be a step toward achieving the goal of population-scale sequencing. However, existing algorithms are limited in their performance because of their frequent memory accesses.
BWA-MEM2 is a popular short-read alignment software package currently used to sequence the DNA. However, it has its limitations. The state-of-the-art alignment has two phases – seeding and extending. During the seeding phase, searches find exact matches of short reads in the reference DNA sequence. During the extending phase, the short reads from the seeding phase are extended. In the current process, bottlenecks occur in the seeding phase. Finding the exact matches slows the process.
The researchers set out to solve the problem of accelerating the DNA sequence alignment. To speed the process, they applied machine learning techniques to create an algorithmic improvement. Their algorithm, BWA-MEME (BWA-MEM emulated) leverages learned indices to solve the exact match search problem. The original software compared one character at a time for an exact match search. The team’s new algorithm achieves up to 3.45x faster speeds in seeding throughput over BWA-MEM2 by reducing the number of instructions by 4.60x and memory accesses by 8.77x. “Through this study, it has been shown that full genome big data analysis can be performed faster and less costly than conventional methods by applying machine learning technology,” said Professor Dongsu Han from the School of Electrical Engineering at KAIST.
The researchers’ ultimate goal was to develop efficient software that scientists from academia and industry could use on a daily basis for analyzing big data in genomics. “With the recent advances in artificial intelligence and machine learning, we see so many opportunities for designing better software for genomic data analysis. The potential is there for accelerating existing analysis as well as enabling new types of analysis, and our goal is to develop such software,” added Han.
Whole genome sequencing has traditionally been used for discovering genomic mutations and identifying the root causes of diseases, which leads to the discovery and development of new drugs and cures. There could be many potential applications. Whole genome sequencing is used not only for research, but also for clinical purposes. “The science and technology for analyzing genomic data is making rapid progress to make it more accessible for scientists and patients. This will enhance our understanding about diseases and develop a better cure for patients of various diseases.”
The research was funded by the National Research Foundation of the Korean government’s Ministry of Science and ICT.
-PublicationYoungmok Jung, Dongsu Han, “BWA-MEME:BWA-MEM emulated with a machine learning approach,” Bioinformatics, Volume 38, Issue 9, May 2022
(https://doi.org/10.1093/bioinformatics/btac137)
-ProfileProfessor Dongsu HanSchool of Electrical EngineeringKAIST
2022.05.10 View 14645 -
3D Visualization and Quantification of Bioplastic PHA in a Living Bacterial Cell
3D holographic microscopy leads to in-depth analysis of bacterial cells accumulating the bacterial bioplastic, polyhydroxyalkanoate (PHA)
A research team at KAIST has observed how bioplastic granule is being accumulated in living bacteria cells through 3D holographic microscopy. Their 3D imaging and quantitative analysis of the bioplastic ‘polyhydroxyalkanoate’ (PHA) via optical diffraction tomography provides insights into biosynthesizing sustainable substitutes for petroleum-based plastics.
The bio-degradable polyester polyhydroxyalkanoate (PHA) is being touted as an eco-friendly bioplastic to replace existing synthetic plastics. While carrying similar properties to general-purpose plastics such as polyethylene and polypropylene, PHA can be used in various industrial applications such as container packaging and disposable products.
PHA is synthesized by numerous bacteria as an energy and carbon storage material under unbalanced growth conditions in the presence of excess carbon sources. PHA exists in the form of insoluble granules in the cytoplasm. Previous studies on investigating in vivo PHA granules have been performed by using fluorescence microscopy, transmission electron microscopy (TEM), and electron cryotomography.
These techniques have generally relied on the statistical analysis of multiple 2D snapshots of fixed cells or the short-time monitoring of the cells. For the TEM analysis, cells need to be fixed and sectioned, and thus the investigation of living cells was not possible. Fluorescence-based techniques require fluorescence labeling or dye staining. Thus, indirect imaging with the use of reporter proteins cannot show the native state of PHAs or cells, and invasive exogenous dyes can affect the physiology and viability of the cells. Therefore, it was difficult to fully understand the formation of PHA granules in cells due to the technical limitations, and thus several mechanism models based on the observations have been only proposed.
The team of metabolic engineering researchers led by Distinguished Professor Sang Yup Lee and Physics Professor YongKeun Park, who established the startup Tomocube with his 3D holographic microscopy, reported the results of 3D quantitative label-free analysis of PHA granules in individual live bacterial cells by measuring the refractive index distributions using optical diffraction tomography. The formation and growth of PHA granules in the cells of Cupriavidus necator, the most-studied native PHA (specifically, poly(3-hydroxybutyrate), also known as PHB) producer, and recombinant Escherichia coli harboring C. necator PHB biosynthesis pathway were comparatively examined.
From the reconstructed 3D refractive index distribution of the cells, the team succeeded in the 3D visualization and quantitative analysis of cells and intracellular PHA granules at a single-cell level. In particular, the team newly presented the concept of “in vivo PHA granule density.” Through the statistical analysis of hundreds of single cells accumulating PHA granules, the distinctive differences of density and localization of PHA granules in the two micro-organisms were found. Furthermore, the team identified the key protein that plays a major role in making the difference that enabled the characteristics of PHA granules in the recombinant E. coli to become similar to those of C. necator.
The research team also presented 3D time-lapse movies showing the actual processes of PHA granule formation combined with cell growth and division. Movies showing the living cells synthesizing and accumulating PHA granules in their native state had never been reported before.
Professor Lee said, “This study provides insights into the morphological and physical characteristics of in vivo PHA as well as the unique mechanisms of PHA granule formation that undergo the phase transition from soluble monomers into the insoluble polymer, followed by granule formation. Through this study, a deeper understanding of PHA granule formation within the bacterial cells is now possible, which has great significance in that a convergence study of biology and physics was achieved. This study will help develop various bioplastics production processes in the future.”
This work was supported by the Technology Development Program to Solve Climate Changes on Systems Metabolic Engineering for Biorefineries (Grants NRF-2012M1A2A2026556 and NRF-2012M1A2A2026557) and the Bio & Medical Technology Development Program (Grant No. 2021M3A9I4022740) from the Ministry of Science and ICT (MSIT) through the National Research Foundation (NRF) of Korea to S.Y.L. This work was also supported by the KAIST Cross-Generation Collaborative Laboratory project.
-PublicationSo Young Choi, Jeonghun Oh, JaeHwang Jung, YongKeun Park, and Sang Yup Lee. Three-dimensional label-free visualization and quantification of polyhydroxyalkanoates in individualbacterial cell in its native state. PNAS(https://doi.org./10.1073/pnas.2103956118)
-ProfileDistinguished Professor Sang Yup LeeMetabolic Engineering and Synthetic Biologyhttp://mbel.kaist.ac.kr/
Department of Chemical and Biomolecular Engineering KAIST
Endowed Chair Professor YongKeun ParkBiomedical Optics Laboratoryhttps://bmokaist.wordpress.com/
Department of PhysicsKAIST
2021.07.28 View 21029 -
A Technology Holding Company Establishes Two Companies Based on Technologies Developed at KAIST
Mirae Holdings is a technology holding company created by four science and technology universities, KAIST, DIGIST (Daegu Gyeongbuk Institute of Science and Technology), GIST (Gwangju Institute of Science and Technology), and UNIST (Ulsan National Institute of Science and Technology) in 2014 to commercialize the universities’ research achievements. The company identifies promising technologies for commercialization, makes business plans, establishes venture capitals, and invests in startup companies.
Over the past year, Mirae Holdings has established two venture companies based on the technologies developed at KAIST. In September 2014, it founded Cresem Inc., a company used the anisotropic conductive film (ACF) bonding technology, which was developed by Professor Kyung-Wook Paik of the Material Science and Engineering Department at KAIST. Cresem provides a technology to bond electronic parts ultrasonically. The company is expected to have 860,000 USD worth of sales within the first year of its launching.
Last June, Mirae Holdings created another company, Doctor Kitchen, with the technology developed by Professor Gwan-Su Yi of the Bio and Brain Engineering Department at KAIST. Doctor Kitchen supplies precooked food, which helps diabetic patients regulate their diet. The company offers a personalized diet plan to customers so that they can effectively manage their disease and monitor their blood sugar level efficiently.
The Chief Executive Officer of Mirae Holdings, Young-Ho Kim, said, “We can assist KAIST researchers who aspire to create a company based on their research outcomes through various stages of startup services such as making business plans, securing venture capitals, and networking with existing businesses.”
Young-Ho Kim (left in the picture), the Chief Executive Officer of Mirae Holdings, holds a certificate of company registration with Sang-Min Oh (right in the picture), the Chief Executive Officer of Cresem.
Young-Ho Kim (left in the picture), the Chief Executive Officer of Mirae Holdings, holds a certificate of company registration with Jae-Yeun Park (right in the picture), the Chief Executive Officer of Dr. Kitchen.
2015.07.29 View 19110 -
KAIST to support the Genetic Donguibogam Research Project for global market entry of a new natural drug produced by Green Cross Corporation HS
In the wake of the spread of the Middle East Respiratory Syndrome (MERS), sales of immune-enhancing products in Korea such as red and white ginseng have risen dramatically. Ginseng is one of Korea’s major health supplement it exports, but due to the lack of precise scientific knowledge of its mechanism, sales of ginseng account for less than 2% of the global market share.
The Genetic Donguibogam Research Project represents a group of research initiatives to study genes and environmental factors that contribute to diseases and to discover alternative treatments through Eastern medicine. The project is being led by KAIST’s Department of Bio & Brain Engineering Professor Do-Heon Lee.
Professor Lee and Chief Executive Officer Young-Hyo Yoo of Green Cross Corporation HS, a Korean pharmaceutical company, signed a memorandum of understanding (MOU), as well as a non-disclosure agreement (NDA) to develop a naturally derived drug with an enhanced ginsenoside, pharmacological compounds of ginseng, for the global market entry of BST204 on June 10, 2015.
Donguibogam is the traditional Korean source for the principles and practice of Eastern medicine, which was compiled by the royal physician Heo Jun and first published in 1613 during the Joseon Dynasty of Korea.
Cooperating with Green Cross Co., HS, KAIST researchers will use a multi-component, multi-target (MCMT)-based development platform to produce the new natural drug, BST204. This cooperation is expected to assist the entry of the drug into the European market.
Green Cross Co., HS has applied a bio-conversion technique to ginseng to develop BST204, which is a drug with enhanced active constituent of aginsenosides. The drug is the first produced by any Korean pharmaceutical company to complete the first phase of clinical trials in Germany and is about to start the second phase of trials.
Professor Do-Heon Lee, the Director of the project said, “Genetic Donguibogam Research Project seeks to create new innovative healthcare material for the future using integrated fundamental technologies such as virtual human body computer modelling and multi-omics to explain the mechanism in which natural ingredients affect the human body.” He continued, “Especially, by employing the virtual human body computer modelling, we can develop an innovative new technology that will greatly assist Korean pharmaceutical industry and make it the platform technology in entering global markets.”
Young-Hyo Yoo, the CEO of Green Cross Co., HS, said, “For a new naturally derived drug to be acknowledged in the global market, such as Europe and the US, its mechanism, as well as its effectiveness and safety, should be proven. However, it is difficult and costly to explain the mechanism in which the complex composition of a natural substance influences the body. Innovative technology is needed to solve this problem.”
Professor Do-Heon Lee (left in the picture), the Director of Genetic Donguibogam Research Project, stands abreast Young-Hyo Yoo (right in the picture), the CEO of Green Cross Co., HS.
2015.06.10 View 14164