Abstrakt. I komparativ genomik är ett införlivande en operation som utbyter två på varandra följande sekvenser av gener i ett genom. Införlivandeavståndet, dvs. det minsta antal införlivanden som krävs för att omvandla ett genom till ett annat, är enligt många studier ett relevant utvecklingsavstånd. Problemet med att beräkna detta avstånd när genom representeras av permutationer, som kallas sortering av Transpositions problem, har införts av Bafna och Pevzner [3] i 1995. Det har naturligtvis varit fokus för ett antal studier, men den beräkningsmässiga komplexiteten i detta problem har förblivit obestämd i 15 år. I detta dokument besvarar vi denna sedan länge öppna fråga genom att bevisa att problemet med sortering genom införlivande är NP-hård. Som en följd av vårt resultat, vi bevisar också att följande problem [8] är NP-hård: ges en permutation π, är det möjligt att sortera π med hjälp av d (π)/3 permutationer, där d b (π) är antalet brytpunkter π?
Den komplicerade sorteringen genom införlivanden var öppen under en lång tid; först nyligen har det visat sig vara NP-hård REF.
Sorting by Transpositions is Difficult
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}