无忧视频

Computer Science Department Publications

The 无忧视频 Computer Science Department seems to have developed an algorithm for productivity. Four papers have recently been accepted for presentation and/or publication.

A paper by math major Bo Zhang 鈥�17 and Assistant Professor of Computer Science Yi-Chieh (Jessica) Wu has been accepted to the International Symposium on Bioinformatics Research and Applications. 鈥淐o-estimation of gene trees and reconciliations under a duplication-loss-coalescence model鈥� focuses on algorithmic capability in tree mapping. 鈥淥ne problem with existing reconciliation methods is that they do not account for error in the evolutionary tree for a gene family,鈥� Wu explains. 鈥淥ur work demonstrates that independent gene tree reconstruction followed by reconciliation degrades the accuracy of our evolutionary predictions. To address this challenge, we developed a probabilistic method for simultaneously reconstructing the gene tree and reconciling it with the species tree, and we demonstrate that this approach outperforms existing methods.鈥�

Beginning in spring 2015, Zhang took the project from concept to publication. 鈥淗e was responsible for deriving much of the math and implemented the majority of the algorithm,鈥� Wu says.

A paper by Odaris Barios-Arciga 鈥�18 (SCR), Noah Marcus 鈥�17, Jasmine Zhu 鈥�19, UC San Diego graduate student John Sarracino 鈥�14, HMC Assistant Professor Ben Wiedermann and UCSD Professor Sorin Lerner has been accepted to the ACM CHI Conference on Human Factors in Computing Systems. The paper,聽鈥淯ser-guided synthesis of interactive diagrams,鈥� presents techniques that transform a static diagram into an interactive one without requiring the user to write code. The CHI conference takes place in Denver in May.

Alex Ozdemir 鈥�17 will travel to Portugal in June to present 鈥淐lustering the space of maximum parsimony reconciliations in the duplication-transfer-loss model鈥� at the Conference on Algorithms for Computational Biology. The paper is the result of several years of research and is co-authored by Michael Sheely 鈥�17, Daniel Bork 鈥�16, Ricson Cheng 鈥�19 (Carnegie Mellon University), Reyna Hulett 鈥�16, Jean Sung 鈥�16, Jincheng Wang 鈥�17 and computer science Professor Ran Libeskind-Hadas.

Like Wu and Zhang鈥檚 work, this team鈥檚 research deals with the problem of inferring how genes can have different evolutionary histories from the species in which they are found. A fundamental problem in computational biology is that of 鈥渞econciling鈥� the evolutionary tree for a gene family with the evolutionary tree for a set of species to explain their differences. Often, the number of 鈥渕ost plausible鈥� reconciliations can be very large, and it grows exponentially. 鈥淭here can be billions of good solutions,鈥� Libeskind-Hadas says. 鈥淣o biologist wants to sort through billions of good solutions.鈥� The team developed fast algorithms for clustering the very large number of possible solutions into a small number of 鈥渂est representative鈥� solutions. The method uses what Libeskind-Hadas calls 鈥渟ome algorithmic trickery鈥� to efficiently find these clusters without explicitly enumerating the exponentially large number of solutions.

Ozdemir, who worked on the research in the fall of 2015, is pursuing an Individual Program of Studies major in computational, mathematical and physical theory. After the trip to Portugal and a visit Spain with family, Ozdemir plans to begin a PhD program in computer science.

A paper by Bork, Sung, Wang, Cheng and Libeskind-Hadas has been accepted to the journal聽Algorithms for Molecular Biology. Titled 鈥淥n the computational complexity of the maximum parsimony reconciliation problem in the duplication-loss-coalescence model,鈥� this work examines another phylogenetic tree reconciliation problem that was first studied by Wu and her collaborators at MIT. That pioneering earlier work left open the question of the computational complexity of the problem. The HMC team was able to prove that the problem is not only computationally hard, but it is even computationally hard to find solutions that approximately optimal. 鈥淭hat means that someone shouldn鈥檛 spend their PhD searching for optimal or even near-optimal algorithms for that specific problem,鈥� Libeskind-Hadas says.