Understanding Two-String Consensus Problem Under Mutation Distance
Delve into the complexity of solving the two-string consensus problem under non-overlapping inversion and transposition distance, as presented in a study regarding biological sequences mutation operations. Explore the defined mutation distance, algorithmic solutions, and bipartite graph constructions relevant to this intriguing problem.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Two-string consensus problem under non- overlapping inversion and transposition distance Toan Thang Ta, Cheng-Yao Lin, Chin Lung Lu ( ) Information Processing Letters 130 (2018) pp. 46-51 Speaker: Kuan-Lin Lai Date: Apr. 09, 2019
Abstract For biological sequences that can be represented as strings over a finite alphabet, inversion and transposition are commonly observed mutation operations. The non-overlapping inversion and transposition distance (also simply called mutation distance) between two strings is defined as the minimum number of non-overlapping inversion and transposition operations used to transform one string into the other. Given two strings of the same length n and a constant c 0, the two-string consensus problem under mutation distance is to determine whether or not there exists a string s such that the mutation distance from s to each input string does not exceed c. In this study, we present an O(n5) time and O(n4) space algorithm to solve this problem.
Two string consensus problem under mutation distance Ex: x = TAGAC y = TAACG c=1 ? = TAGAC or TAACG
Mutation table z = TAGAC inversion table tranpostion table
Matched pair Ex: x = TAGAC y = TAACG c=1 ? = TAGAC or TAACG
Algorithm For each i, we construct a bipartite graph ??= (??,??,??) ??= ?? ??= ?? If ? ? ? and ? ? ?, then create an edge (?,?) in ?? ? ?? ? ?? ? ??? ?? ? ??? ?? ? ? ? ? ??? ? Q? ?? ?? ?? ??? ? ? ? ?? ?? ??
Algorithm (?,?)in ??is classified into one of 16 types II, IH, IT, IQ, HI, HH, HT, HQ TI, TH, TT, TQ, QI, QH, QT, QQ Case by Case !!
??? ??? ??? ??? ??? Algorithm ?1 ??? ??? ??? ??? x=AGC y=GCT ??? ??? ??? ??? ?2 ??? ??? ??? ??? ??? ??? ?3 ??? ???
Algorithm II => II, IQ, QI, QQ IH => IH, IT, QH (Similar as HI) IT => QT, IQ, QQ (Similar as TI) HH => HH, HT, TH, TT HT => HT, TT, HQ (Similar as HT) TT => TT, QT, TQ, QQ
Algorithm IQ => II, IH, IQ, QQ (Similar as QI) HQ => HI, HH, HQ, TI, TH, TQ (Similar as QH) TQ => TI, TH, TQ, QQ (Similar as QT) QQ => II, IH, IQ, HI, HH, HQ, QI, QH, QQ
Complexity Time complexity: ?(?5) ( ?? + ?? + ?? + ?? + ?? + ?? + ?? + ?? + ?? ) ?(1) + ( ?? + ?? + ?? + ?? + ?? + ?? ? ?4* ? 1 + ? ?2* ? ? + ? 1 * ? ?2= ? ?4 ? ? + ?? ? ?2= ) Space complexity: ?(?4)
Algorithm ? ? ? ? ? 1 ? ? ? ? ? ? 1 ? ?? ?? ?? ?? ??
Algorithm ? ? ? ? ? ? 1 ? ? ? ? ? + 1 ? 1 ? ?? ?? ?? ?? ??
