Nir Yosef

Closed (1) Spectral graph algorithms for single-cell lineage tracing

Applications for fall 2021 are now closed for this project.

Cellular lineages are important across biology -- for example, how a single-cell becomes a full human, or how your specialized blood cells are constantly replenished throughout your life. Understanding these temporal processes are critical for understanding both normal physiology and how things might go wrong in disease.

Recently, our lab (the Yosef lab) has collaborated with groups at UCSF & MIT to develop a novel CRISPR/Cas9-based system for tracing cellular lineages. This technology allows researchers to follow the relationships amongst populations of cells over long periods of time, shedding light on how processes like tumorigenesis and embryogenesis unfold. The Cassiopeia team in the Yosef lab leads efforts to develop computational tools for processing and analyzing this type of data. Cassiopeia is a publicly available codebase, hosted on Github at

We are constantly generating new algorithms with theoretical guarantees and are investigating their performance on both simulated and real datasets. Such algorithms bridge the gap between optimization, molecular phylogenetics, and unsupervised learning.

For more information regarding this research opportunity, see the link to the document at the bottom of this page.

The selected candidate will help implement, benchmark, and eventually extend a spectral graph-based algorithm for reconstruction of cellular phylogenies (i.e., models of cell lineages) with theoretical guarantees. This algorithm is based on the Spectral Neighbor-Joining algorithm ( with adaptations to the nuances of our single-cell lineage tracing datasets.

A successful applicant will have the opportunity to work closely within a dynamic team of PhD students and research technicians to complete this project. Along the way, they will utilize Cassiopeia, contribute code to our software suite, present results to our group, and eventually begin to extend this work in a more independent research capacity. We encourage students to earn course credit through this research experience.

Beyond the tangible skills of implementing an algorithm, developing code in a team-based environment, and contributing results to an eventual publication, we also anticipate the successful candidate to gain familiarity with CRISPR/Cas9-based engineering and an exciting field in computational biology that will surely grow over the coming years.

Day-to-day supervisor for this project: Matthew Jones, Graduate Student

Qualifications: REQUIRED: -A solid background in algorithm design and analysis, at a minimum having completed CS170 or a course equivalent. -Completed coursework in linear algebra, such as through Math 54, CS189, EE16A/B, Math 110, EE127, or equivalent. -Software engineering experience using object oriented programming in Python. Knowledge of how to use and write Jupyter notebooks is a plus. -Effective writing and communication skills. -Commitment of at least 8 hours per week. The selected applicant must attend our weekly Cassiopeia meetings, and ideally will attend the Yosef Lab group meetings as well. DESIRED: -Familiarity with molecular phylogenetics, such as through CS176. -Knowledge of advanced statistical concepts, such as through CS189 or upper-division statistics courses. -Familiarity with spectral theory and graph partitioning algorithms. While no previous biology research experience is required, we also encourage applicants with a familiarity, or strong interest in learning about, molecular biology, CRISPR/Cas9-engineering, single-cell RNA-seq, and generally immersing themselves in exciting biological literature.

Weekly Hours: 6-8 hrs

Related website:
Related website: