Phillip Compeau
Associate Teaching Professor
Assistant Department Head
Computational Biology Department
Carnegie Mellon University
Publications - Journal paper
Filter by type:
We consider four families of pancake graphs, which are Cayley graphs, whose vertex sets are either the symmetric group on n objects or the hyperoctahedral group on n objects and whose generating sets are either all reversals or all reversals inverting the first k elements (called prefix reversals). We find that the girth of each family of pancake graphs remains constant after some small threshold value of n.
Background
The introduction of the double cut and join operation (DCJ) caused a flurry of research into the study of multichromosomal rearrangements. However, little of this work has incorporated indels (i.e., insertions and deletions of chromosomes and chromosomal intervals) into the calculation of genomic distance functions, with the exception of Braga et al., who provided a linear time algorithm for the problem of DCJ-indel sorting. Although their algorithm only takes linear time, its derivation is lengthy and depends on a large number of possible cases.
Results
We note the simple idea that a deletion of a chromosomal interval can be viewed as a DCJ that creates a new circular chromosome. This framework will allow us to amortize indels as DCJs, which in turn permits the application of the classical breakpoint graph to obtain a simplified indel model that still solves the problem of DCJ-indel sorting in linear time via a more concise formulation that relies on the simpler problem of DCJ sorting. Furthermore, we can extend this result to fully characterize the solution space of DCJ-indel sorting.
Conclusions
Encoding indels as DCJ operations offers a new insight into why the problem of DCJ-indel sorting is not ultimately any more difficult than that of sorting by DCJs alone. There is still room for research in this area, most notably the problem of sorting when the cost of indels is allowed to vary with respect to the cost of a DCJ and we demand a minimum cost transformation of one genome into another.
Online science education needs a new revolution.
In a flipped classroom, students complete automated modules to replace a traditional lecture, allowing the time devoted for the lecture to be devoted to constructive tasks reinforcing student knowledge. Yet although the flipped classroom offers a compelling approach for fostering a constructivist, student-centric learning environment, research on the efficacy of flipped classes has been mixed. For that matter, is it possible to successfully flip a classroom in an advanced, heavily specialized course like a bioinformatics algorithms course? Over the past several years, the author has implemented a flipped version of such a course and will discuss some of the successes and pitfalls encountered.
Much of the fundamental work on the problem of assembling genomes from short reads is based upon a structure called a de Bruijn graph and finding an Eulerian path in this graph. In this review paper, we describe this approach and detail how it has been applied to genome assembly algorithms.