Ying’s algorithm reconstructs the spread of an entity such as an illness from single or multiple sources. Credit: Lei Ying
With an approach that combines big data, network science and stochastic systems, a Michigan Engineering professor is working to develop algorithms that can quickly and accurately identify COVID-19 “patient zero” as the virus spreads to new places or resurges, and reconstruct its spread with limited information.
Lei Ying, professor of electrical engineering and computer science, is using a wide array of data that might include, for example, human mobility data, social network data and genetic network analysis. This is a new application of an NSF project that Ying and his team have been working on for several years.
The project focuses on establishing a theoretical framework for locating the source of anything that has already spread so widely, it can seem like finding the original stalk of straw in a haystack.
What has spread might be a rumor on the Internet, an emotion prompted by an image on social media, or in the case of COVID-19, a viral germ.
Locating the origin and recovering the spreading history of an epidemic can help identify how the disease was transmitted, says Ying, and in turn, reveal modes of transmissions, dangerous exposure locations and high-risk individuals. Citing the 2009 H1N1 virus that resulted in between 151,000 and 575,000 deaths as a case where this research could have saved numerous lives, this technology could provide important information as the nation and world reopen.
“Ideally, it would be possible to provide a complete history of direct lines of infection to reconstruct an outbreak,” Ying said. “Realistically, that is impossible. Even coming close to tracing exact lines of transmission could take more resources, both in terms of time and cost, than is reasonable. However, by looking at a smaller set of key clues, we can come close.
“Our algorithm is designed to be used with imperfect contact tracing, so it provides a more accurate picture of the spreading with partial or limited contact tracing information.”
Ying created a reconstruction algorithm based on only partial observations that shows superior performance over existing algorithms and heuristic methods. Tested on the Western States Power Grid and Internet autonomous systems network, they are now turning their attention to tracking the path of COVID-19.
As society reopens and faces the threat of additional waves of the illness, tracking the spread of infections in specific locations could lead to swifter action in terms of quarantining individuals, ultimately saving lives.