Brown CS News

For a blog post by Sorin about the history of the research below, please click here.

The European Symposium on Algorithms (ESA) recently announced that Julie Nguyen Brown Professor of Computational and Mathematical Sciences and Professor of Computer Science Sorin Istrail, along with collaborators, won the ESA 2021 Test-of-Time Award for their 2001 paper “SNPs Problems, Complexity, and Algorithms.” The award recognizes “excellent papers in algorithm research that were published ... 19-21 years ago and which are still influential and stimulating for the field today,” according to the ESA. Giuseppe Lancia of the University of Udine, Vineet Bafna of UC San Diego, Ross A. Lippert of DE Shaw Research, and Russell Schwartz of Carnegie Mellon University co-authored the paper with Sorin. The research presented in the paper was conducted while the authors worked in private industry at Celera Genomics, where Sorin was Senior Director of Informatics Research.

Sorin’s paper dealt with the problem of haplotype phasing, i.e., constructing diploid (maternal and paternal) haplotypes of a single individual from genome sequencing data, a record of about 4 million SNPs / genetic variations. Genomic variation of SNPs and haplotypes is fundamental in the search of genetic determinants of health and disease. The paper presented an algorithmic theory of SNPs and haplotype reconstruction, using the rigorous methods of computer science to define and solve algorithmic problem formulations that capture computational challenges – islands of tractability and computational intractability – involved in these very large genomic and biological databases.

“This Celera paper and others it gave rise to are a direct result of the pioneering efforts of our wonderful SNPs and haplotypes team,” Sorin says. “Celera offered a once-in-a-lifetime experience for many of us, a synergy that could only arise through technically brilliant colleagues and inspiring company leadership. Driven by the beauty of exceedingly difficult computational biology problems emerging from the Human Genome Project, the first algorithmic assembly of the sequence of the human genome stood the test of time. In the 20 years since our ESA 2001 paper, members of the team have moved on from Celera. Partnering with their students and collaborators, they’ve built on their groundbreaking work, providing pillars of computer science contributions to the field.”

Sorin’s research at Brown focuses on SNPs and haplotypes algorithms, the regulatory genome, and protein folding algorithms; theoretical computer science, algorithms and computational complexity; and statistical physics. He’s the former Director of the Center for Computational Molecular Biology at Brown University. Before joining Brown, he served as Senior Director and then Head of Informatics Research at Celera Genomics, where his group played a central role in the construction of the sequence of the human genome. In 2000, Sorin obtained the negative solution (computational intractability) of the Three-Dimensional Ising Model Problem.

For more information, click the link that follows to contact Brown CS Communications Manager Jesse C. Polhemus.