Efficient Synthesis of Mutants Using Genetic Crosses

Simple item page
dc.contributor.authorPratapa, Adityaen
dc.contributor.authorJalihal, Amogh P.en
dc.contributor.authorRavi, S. S.en
dc.contributor.authorMurali, T. M.en
dc.date.accessioned2020-11-03T14:26:58Zen
dc.date.available2020-11-03T14:26:58Zen
dc.date.issued2018-06-29en
dc.description.abstractThe genetic cross is a fundamental, flexible, and widely-used experimental technique to create new mutant strains from existing ones. Surprisingly, the problem of how to efficiently compute a sequence of crosses that can make a desired target mutant from a set of source mutants has received scarce attention. In this paper, we make three contributions to this question. First, we formulate several natural problems related to efficient synthesis of a target mutant from source mutants. Our formulations capture experimentally-useful notions of verifiability (e.g., the need to confirm that a mutant contains mutations in the desired genes) and permissibility (e.g., the requirement that no intermediate mutants in the synthesis be inviable). Second, we develop combinatorial techniques to solve these problems. We prove that checking the existence of a verifiable, permissible synthesis is NP-complete in general. We complement this result with three polynomial time or fixed-parameter tractable algorithms for optimal synthesis of a target mutant for special cases of the problem that arise in practice. Third, we apply these algorithms to simulated data and to synthetic data. We use results from simulations of a mathematical model of the cell cycle to replicate realistic experimental scenarios where a biologist may be interested in creating several mutants in order to verify model predictions. Our results show that the consideration of permissible mutants can affect the existence of a synthesis or the number of crosses in an optimal one. Our algorithms gracefully handle the restrictions that permissible mutants impose. Results on synthetic data show that our algorithms scale well with increases in the size of the input and the fixed parameters.en
dc.description.sponsorshipNational Science Foundation grants CCF-1617678, ACI-1443054, and IIS-1633028 supported this work.en
dc.format.extent23 pagesen
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1101/359281en
dc.identifier.urihttp://hdl.handle.net/10919/100776en
dc.language.isoenen
dc.rightsCreative Commons Attribution 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.titleEfficient Synthesis of Mutants Using Genetic Crossesen
dc.title.serialVirginia Techen
dc.typeArticleen
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
359281v1.full.pdf
Size:
614.76 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Scholarly Works, Computer Science