Research
The focus of my work is the design and analysis of algorithms for practical problems, mostly in bioinformatics.
Network flow decomposition with application to multiassembly
The decomposition of a flow network into a minimum number of paths is a NP-hard problem that is also a natural model for multiassembly problems like RNA transcript and viral quasispecies assembly. My dissertation addresses both practical and theoretical sides of this problem.
Under review:
- Manuel Cáceres, Massimo Cairo, Andreas Grigorjew, Shahbaz Khan, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu, Lucia Williams. “Width Helps and Hinders When Splitting Flows.”
Peer reviewed publications:
Fernando Dias, Lucia Williams, Alexandru I. Tomescu, Brendan Mumey. “Fast, Flexible, and Exact Flow Decompositions via ILP,” Accepted at RECOMB 2022.
Shahbaz Khan, Milla Kortelainen, Manuel Cáceres, Lucia Williams, Alexandru I. Tomescu, “Safety and Completeness in Flow Decompositions for RNA Assembly,” Accepted at RECOMB 2022.
Lucia Williams, Alexandru I. Tomescu, Brendan Mumey, “Flow Decomposition With Subpath Constraints,” 21st International Workshop on Algorithms in Bioinformatics (WABI), Aug. 20212.
Lucia Williams, Gillian Reynold, Brendan Mumey, “RNA Transcript Assembly Using Inexact Flows,” IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Nov. 2019.
Posters:
General-audience presentations:
- I was a finalist at the Montana State University Three Minute Thesis competition in February 2022. Here is my single slide and three minute talk script.
Maximal haplotype blocks with unknowns and pangenome SNPs
We are extending recent progress on the problem of finding maximal perfect haplotype blocks from a set of SNP-resolved haplotypes to include unknown data and to work in a pangenomic setting.
Peer reviewed publications:
- Lucia Williams, Brendan Mumey, “Maximal Perfect Haplotype Blocks with Wildcards,” iScience, vol 101149. 2020.
- Lucia Williams, Brendan Mumey, “Extending Maximal Perfect Haplotype Blocks to the Realm of Pangenomics,” Algorithms for Computational Biology (AlCoB) 2020, Apr. 2020. Lecture Notes in Computer Science, vol 12099.
Recorded talks:
- Sequencing, Finishing and Analysis in the Future meeting, December 2020. “Investigating Selection in Pangenomes with Haplotype Blocks.”
Shape reconstruction using topological descriptors
We are developing algorithms to reconstruct shapes from topological descriptors such as persistence diagrams and Euler characteristic curves.
Peer reviewed publications:
- Robin Lynne Belton, Brittany Terese Fasy, Rostik Mertz, Samuel Micka, David L. Millman, Daniel Salinas, Anna Schenfisch, Jordan Schupbach, Lucia Williams, “Reconstructing Embedded Graphs from Persistence Diagrams,” Computational Geometry, 2020.
Workshop papers:
- Brittany Terese Fasy, Samuel Micka, David L. Millman, Anna Schefisch, Lucia Williams, “Challenges in Reconstructing Shapes from Euler Characteristic Curves”, in 28th Annual Fall Workshop on Computational Geometry.