資工系專題演講(Lecture)
日期(date)/時間(time)：113年11月28日(四/Thu)13:10~15:00
地點(location)：電綜大樓B101演講廳
演講者(speaker)：Professor Guillaume Fertin
服務單位(job)：Professor in LS2N/Computer Science Department, Nantes Université, France
講題(topic)：Genome Rearrangements: an Algorithmic Tour
摘要(summary)：
In this talk, I will present a series of algorithmic results concerning the Genome Rearrangements problem. This general problem occurs in the field of comparative genomics, where one aims at estimating the evolutionary distance between two species.

In this context, a genome is represented as an ordered set of genes. More precisely, if no gene occurs more than once, a genome having n genes is modeled as a permutation π over {1,2…n}, e.g. π = 5 3 1 4 2. An additional information may exist on the genome, under the form of a sign (+ or -) given to each gene, e.g. π = +5 +3 -1 +4 -2. In the latter case, we will talk about signed genomes, while in the former we will talk about unsigned genomes.

A genome rearrangement corresponds to a large scale evolutionary event, in which one or several segments of a genome is/are taken, possibly reversed, and then reincorporated at some location in the genome. One such rearrangement is called reversal, in which a segment is cut, reversed, and reincorporated at the same location. For instance, π’= 5 2 4 1 3 is obtained from π = 5 3 1 4 2 after one reversal : cut before the second gene and after the last gene, and reverse the corresponding segment.

The general problem which I will discuss is thus the following : given two genomes G₁ and G₂ and a set S of allowed genome rearrangements, determine the minimum number of rearrangements from S that are necessary to obtain G₂, starting from G₁. I will present a series of algorithmic results on this problem, both in signed and unsigned genomes. First, I will focus on the case where S contains only reversals. I will then also explore other genome rearrangements such as prefix reversals and multi-cut rearrangements.

與工程認證核心能力關聯性：
■培養持續學習與獨立學習的習慣與能力