Please use this identifier to cite or link to this item:
Type: Artigo
Title: A cubic algorithm for the generalized rank median of three genomes
Author: Chindelevitch, Leonid
La, Sean
Meidanis, Joao
Abstract: The area of genome rearrangements has given rise to a number of interesting biological, mathematical and algorithmic problems. Among these, one of the most intractable ones has been that of finding the median of three genomes, a special case of the ancestral reconstruction problem. In this work we re-examine our recently proposed way of measuring genome rearrangement distance, namely, the rank distance between the matrix representations of the corresponding genomes, and show that the median of three genomes can be computed exactly in polynomial time O(n omega), where omega <= 3, with respect to this distance, when the median is allowed to be an arbitrary orthogonal matrix.ResultsWe define the five fundamental subspaces depending on three input genomes, and use their properties to show that a particular action on each of these subspaces produces a median. In the process we introduce the notion of M-stable subspaces. We also show that the median found by our algorithm is always orthogonal, symmetric, and conserves any adjacencies or telomeres present in at least 2 out of 3 input genomes.ConclusionsWe test our method on both simulated and real data. We find that the majority of the realistic inputs result in genomic outputs, and for those that do not, our two heuristics perform well in terms of reconstructing a genomic matrix attaining a score close to the lower bound, while running in a reasonable amount of time. We conclude that the rank distance is not only theoretically intriguing, but also practically useful for median-finding, and potentially ancestral genome reconstruction
Subject: Algoritmo cúbico
Country: Reino Unido
Editor: Springer Nature
Rights: Aberto
Identifier DOI: 10.1186/s13015-019-0150-y
Date Issue: 2019
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000477647300001.pdf3.71 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.