ABSTRACT Att hitta genomiskt avstånd baserat på genordning är ett klassiskt problem i genomomläggningar. Effektiva exakta algoritmer för genomiska avstånd baserade på inversioner och/eller translokaliseringar har hittats men är komplicerade av speciella fall, sällsynta i simuleringar och empiriska data. Vi söker en universell operation som ligger till grund för en mer inkluderande uppsättning evolutionära operationer och som ger ett dragbart genomiskt avstånd med enkel matematisk form. Resultat: Vi studerar en universell dubbel-och-join drift som står för inversioner, translokaliseringar, fissioner och fusioner, men också producerar cirkulära intermediärer som kan återabsorberas. Det genomiska avståndet, som kan beräknas i linjär tid, ges av antalet brytpunkter minus antalet cykler (b − c) i jämförelsediagrammet för de två genomen; antalet hinder går inte in i det. Utan att ändra formeln kan vi ersätta generering och återabsorption av en cirkulär intermediär med ett generaliserat införlivande, vilket motsvarar ett blockutbyte, med vikt två. Vår enkla algoritm omvandlar en multilinjär kromosomgenom till en annan i minsta avstånd.
För att förenkla de befintliga algoritmerna, Yancopooulos et al. uppfann dubbelskärning och gå med operatör, som kan simulera reverseringar och block utbyten (en mer generaliserad form av ett införlivande), vilket resulterar i en enkel och effektiv algoritm REF.
Efficient sorting of genomic permutations by translocation , inversion and block interchange
{'venue': 'Bioinformatics', 'journal': 'Bioinformatics', 'mag_field_of_study': ['Medicine', 'Computer Science']}