Abstract-Vi studerar tandem dupliceringsavståndet mellan binära sekvenser och deras rötter. Med andra ord är mängden av intresse antalet tandem dubblering av formulär x = en bc → y = en bbc, där x och y är sekvenser och a, b och c är deras delsträngar, som behövs för att generera en binär sekvens av längd n från en kvadratfri sekvens från uppsättningen {0, 1, 01, 10, 010, 101}. Detta problem är ett begränsat fall av att hitta duplicerings-/deduplikationsavståndet mellan två sekvenser, definierat som det minsta antalet duplicerings- och dedupliceringsoperationer som krävs för att omvandla den ena sekvensen till den andra. Vi betraktar både exakta och ungefärliga tandem dubbleringar. För exakt duplicering, som anger det maximala avståndet till roten av en sekvens av längd n av f (n), bevisar vi att f (n) = (n). Vid ungefärlig dubblering, där en β-fraktion av symboler kan kopieras felaktigt, visar vi att det maximala avståndet har en skarp övergång från linjär i n till logaritmisk vid β = 1/2. Vi studerar också dupliceringsavståndet till roten för den uppsättning sekvenser som uppstår från en given rot och för speciella klasser av sekvenser, nämligen De Bruijn sekvenser, Thue-Morse sekvens, och Fibonacci ord. Problemet är motiverat av genomiska tandem duplicering mutationer och det minsta antalet tandem duplicering händelser som krävs för att generera en given biologisk sekvens.
Ett av de mest relevanta dokumenten för detta arbete är studien av tandem duplicering avstånd till roten för binära strängar REF.
Duplication Distance to the Root for Binary Sequences
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Biology']}