Key points are not available for this paper at this time.
Wir präsentieren eine neue Methode zur Berechnung von multiplen Sequenzanpassungen (MSAs). Der Input für unser Problem sind n Proteinsequenzen. Wir gehen davon aus, dass die Sequenzen miteinander verwandt sind und dass es einen unbekannten evolutionären Baum gibt, der der MSA entspricht. Ein Vorteil unserer Methode ist, dass die Bewertung in Bezug auf diesen phylogenetischen Baum erfolgen kann, auch wenn die Baumstruktur selbst unbekannt bleiben kann. Anstatt einen evolutionären Baum zu berechnen, müssen wir nur eine zirkulare Tour des Baums berechnen, die über einen Traveling-Salesman-Problemlösungsalgorithmus (TSP) bestimmt wird. Unser Algorithmus kann eine nahezu optimale MSA berechnen und hat eine Leistungsgarantie von n-1/n.opt (wobei opt der optimale Score der MSA ist). Der Algorithmus läuft in O(k/sup 2/n/sup 2/) Zeit, wobei k die Länge der längsten Eingabesequenz ist. Von dort aus verbessern wir die Anpassung weiter. Experimentelle Ergebnisse werden am Ende gezeigt.
Korostensky et al. (Mon,) haben diese Frage untersucht.