Research Summary

deblasio_dan_croppedMy research interest are broadly in algorithm design and analysis, and I take inspiration from biological problems. Many times this not only leads to an interesting algorithmic result, but a useful biological tool (see Software).

I am currently a Lane Fellow in the Computational Biology Department at Carnegie Mellon University working with Carl Kingsford.

I was previously a PhD student in the Computer Science Department at the University of Arizona working with John Kececioglu and a student in the CS Department Department at the University of Central Florida working with Shaojie Zhang.

In the past my work has focused mainly on multiple sequence alignment problems. Most recently I worked on improving accuracy of protein multiple sequence alignments. Multiple sequence alignment is a fundamental step in bioinformatics, but the problem is NP-complete. Because of the importance of the result and complexity of the multiple sequence alignment problem many algorithms exist to find high quality alignments in practice. Each of these algorithms has a large number of tunable parameters that can greatly affect the quality of the computed alignment. Most users rely on the default parameter choices, which produce the best alignments on average, but produce poor alignments for some inputs. We developed a process called parameter advising which selects parameter choices that produces a high quality alignment for the input. To accomplish this candidate alignments are produced using each of the parameter choices in an advising set, the accuracy of these candidate alignments is then estimated using an advising estimator, the candidate alignment with the highest estimated accuracy is then selected for the user. To estimate the alignment accuracy we developed Facet (Feature-based accuracy estimator) which is a linear combination of efficiently-computable feature functions. We have found that learning an optimal advisor (selecting both the estimator coefficients and the set of parameter choices) is NP-complete. We expanded this result to show that finding the estimator coefficients or the estimator set independently is also NP-complete. In practice, we have methods to find close-to optimal advisors. We are working on ways to improve the accuracy of these parameter advisors.

I have also worked on improving the memory consumption of secondary structure conscious RNA multiple sequence alignment (see PMFastR) and high throughput phylogeny filtering (see SiClE).

“Locality sensitive hashing for the edit distance” conditionally accepted to ISMB/ECCB 2019

Related to the work we presented at ISMB last year, our new work on making a new hashing scheme that improves on Jaccard and Hamming distances for searching large sequences was recently conditionally accepted to ISMB/ECCB 2019 in Basel, Switzerland. This is work with Guillaume Marçais, Carl Kingsford, and Prashant Pandey. A preprint of the manuscript is on bioRxiv (see Publications).

ISCB-SC 2018 Symposia Article Published

Our editorial describing the symposia that were hosted by the ISCB Student Council over 2018 calendar year was recently published in F1000 Research. I am proud to say this is the first year I attended 2 out of the 3. While I was not a primary organizer for any of the events, all three were well received and the symposia chairs, the committee members, and all of the attendees are to thank.

With the publication of this article I am also ending my tenure on the ISCB-SC Executive Team, which has been a great experience.

Biological Data Science at Cold Spring Harbor Laboratory

I have been invited to give a talk at the Cold Spring Harbor Laboratory Biological Data Science meeting (#biodata18) November 7-10. My talk is preliminarily titled “Building an automated bioinformatician—More accurate, large-scale genomic discovery using parameter advising”.

Continue reading “Biological Data Science at Cold Spring Harbor Laboratory”

StringBio 2018

I will be giving a talk at the StringBio Workshop at UCF at the end of October. The workshop runs from the 25th to the 27th. I am scheduled to talk on the 26th in the afternoon. I am planning to talk about multiple sequence alignment accuracy estimation using Facet in the context of parameter advising. My slides are available here.

My colleague Guillaume Marçais is also speaking at the meeting, likely about methods related to minimizer ordering (some of which is joint with myself, Carl Kingsford, and others).

Workshop on the Future of Algorithms in Biology

I am part of the organizing team for the Workshop on the Future of Algorithms in Biology, an NSF-funded conference being held here at CMU on September 28 and 29. The slate of talks includes 15 speakers from a wide range of disciplines as well as shorter lightning talks, posters (including my own) and a panel discussion. More information is available on the FAB 2018 website.