### Abstract

Cancer is an evolutionary process characterized by the accumulation of somatic mutations in a population of cells that form a tumor. One frequent type of mutations are copy number aberrations, which alter the number of copies of genomic regions. The number of copies of each position along a chromosome constitutes the chromosome’s copy-number profile. Understanding how such profiles evolve in cancer can assist in both diagnosis and prognosis. We model the evolution of a tumor by segmental deletions and amplifications, and gauge distance from profile a to b by the minimum number of events needed to transform a into b. Given two profiles, our first problem aims to find a parental profile that minimizes the sum of distances to its children. Given k profiles, the second, more general problem, seeks a phylogenetic tree, whose k leaves are labeled by the k given profiles and whose internal vertices are labeled by ancestral profiles such that the sum of edge distances is minimum. For the former problem we give a pseudo-polynomial dynamic programming algorithm that is linear in the profile length, and an integer linear program formulation. For the latter problem we show it is NP-hard and give an integer linear program formulation. We assess the efficiency and quality of our algorithms on simulated instances.

Original language | English (US) |
---|---|

Title of host publication | Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings |

Editors | Martin Frith, Christian Nørgaard Storm Pedersen |

Publisher | Springer Verlag |

Pages | 137-149 |

Number of pages | 13 |

ISBN (Print) | 9783319436807 |

DOIs | |

State | Published - Jan 1 2016 |

Externally published | Yes |

Event | 16th International Workshop on Algorithms in Bioinformatics, WABI 2016 - Aarhus, Denmark Duration: Aug 22 2016 → Aug 24 2016 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9838 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 16th International Workshop on Algorithms in Bioinformatics, WABI 2016 |
---|---|

Country | Denmark |

City | Aarhus |

Period | 8/22/16 → 8/24/16 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Copy-number evolution problems: Complexity and algorithms'. Together they form a unique fingerprint.

## Cite this

*Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Proceedings*(pp. 137-149). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9838 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-43681-4_11