Special note: CSIS seminar series talks will now be live-streamed using Zoom [help]. Modality options will be included in future seminar announcements. If you attend a face-to-face talk, we’d ask that you please practice social distancing, and strive to maintain >= 1m distance between audience members [WHO info].

Speaker:

Lena Collienne, Biological Data Science Lab, Department of Computer Science, University of Otago

Title:

The complexity of computing nearest neighbour interchange distances between ranked phylogenetic trees

Date:

Friday 24th April

Modalities:

Zoom streaming (full invitation below)

Abstract:

Many popular algorithms for searching the space of leaf-labelled (phylogenetic) trees are based on tree rearrangement operations. Under any such operation, the problem is reduced to searching a graph where vertices are trees and (undirected) edges are given by pairs of trees connected by one rearrangement operation (sometimes called a move). Most popular are the classical nearest neighbour interchange, subtree prune and regraft, and tree bisection and reconnection moves. The shortest path problem, however, is NP-hard in each of these graphs, making tree inference and comparison algorithms challenging to design in practice. Although ranked phylogenetic trees are one of the central objects of interest in applications, the computational complexity of the shortest path problem for these trees remained unsolved for decades. In this talk, we settle this problem for the ranked nearest neighbour interchange operation by establishing that the complexity depends on the weight difference between two types of tree rearrangement operations (rank moves and edge moves) in this graph, and varies from quadratic to NP-hard. In particular, our result provides the first example of a phylogenetic tree rearrangement operation for which shortest paths, and hence the distance, can be computed efficiently. Specifically, our algorithm scales to trees with thousands of leaves.

Biography:

Lena is PhD student in the Biological Data Science group. Her research interests are in mathematical phylogenetics, especially in investigating the space of ranked phylogenetic trees.

Zoom Invitation

Join from PC, Mac, iOS or Android: Join from PC, Mac, iOS or Android: https://otago.zoom.us/j/295141083?pwd=amNiUFFEZ2pHbTdGdEYyeGR2SVVKQT09

Password: You should have received this from the csis seminars list on 20th April.  If not contact Dr Steven Livingstone for the password: s.livingstone@otago.ac.nz

Or join by phone: If calling from within New Zealand, dial: 09 884 6780 or 04 886 0026 (Toll charges may apply)
Meeting ID: 295 141 083
Password: As above
If calling from outside New Zealand, please see list of available international numbers: https://blogs.otago.ac.nz/zoom/phone/

Or join from a H.323/SIP room system (e.g.LifeSize, Polycom, Tandberg, Sony) dial: 162.255.37.11 or 162.255.36.11
Then enter Meeting ID: 295 141 083
Password: As above
For more info on H323/SIP room connections, please see: https://blogs.otago.ac.nz/zoom/h323

For more info on joining a Zoom meeting, please see our help site: https://blogs.otago.ac.nz/zoom/how-to-join-a-zoom-meeting-step-by-step/

For any questions or help with Zoom, please contact eConferencing on econferencing@otago.ac.nz or call either +64 3 479 8440 / +64 3 479 8997 during normal work hours.