Imperial College London
Portrait Picture

DrLeonidChindelevitch

Faculty of Medicine, School of Public Health

Lecturer in Infectious Disease Epidemiology
 
 
 
//

Contact

 

l.chindelevitch Website

 
 
//

Location

 

Sir Michael Uren HubWhite City Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Meidanis:2021:10.1016/j.laa.2020.10.030,
author = {Meidanis, J and Chindelevitch, L},
doi = {10.1016/j.laa.2020.10.030},
journal = {Linear Algebra and Its Applications},
pages = {394--414},
title = {Fast median computation for symmetric, orthogonal matrices under the rank distance},
url = {http://dx.doi.org/10.1016/j.laa.2020.10.030},
volume = {614},
year = {2021}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - Biological genomes can be represented as square, symmetric,orthogonal, 0-1 matrices. It turns out that the rank distanceapplied to two genome matrices has a biological significance:it is related to the smallest number of basic rearrangementmutations, such as reversals, translocations, transpositions(taken with weight 2), etc. that explain the differencesbetween the two genomes. Therefore, closer genomes willproduce smaller rank distances.An important tool in this context is the median problem:given three genomes A, B, and C, find a fourth genome Mthat minimizes d(A, M) + d(B, M) + d(C, M). For genomematrices, the computational complexity of this problem iscurrently unknown. However, for orthogonal matrices, thereare fast algorithms that solve it exactly.One such algorithm uses a “walk towards the median”paradigm. Starting from any of the input matrices, say, B, thealgorithm produces rank-1 “steps”, which are rank-1 matricesthat, added to B, decrease its rank distance to both A and Csimultaneously. It can be shown that such steps always existfor orthogonal matrices, and can be found in polynomial time.The algorithm stops when no more improvement can be made,which is equivalent to saying that B lies between A and C interms of the rank distance (the triangle inequality becomesan equality). There is an O(nω+1) algorithm implementingthis idea, where ω is the matrix multiplication exponent.Here we propose a novel scheme that works for symmetric orthogonal matrices, and produces a median, also guaranteedto be symmetric, in O(nω) time.There is another O(nω) time algorithm that produces theso-called MI median, which agrees with the majority in thesubspaces where A = B, B = C, or C = A, and is equalto the identity in the orthogonal complement of the sum ofthese subspaces. However, this algorithm produces a differentmedian, and has only been proved to be correct for genomicmatrices. The algorithm we present here is more general.
AU  - Meidanis,J
AU  - Chindelevitch,L
DO  - 10.1016/j.laa.2020.10.030
EP  - 414
PY  - 2021///
SN  - 0024-3795
SP  - 394
TI  - Fast median computation for symmetric, orthogonal matrices under the rank distance
T2  - Linear Algebra and Its Applications
UR  - http://dx.doi.org/10.1016/j.laa.2020.10.030
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000615183800024&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - https://www.sciencedirect.com/science/article/pii/S0024379520305139?via%3Dihub
UR  - http://hdl.handle.net/10044/1/88369
VL  - 614
ER  -
Download