MUSCLE (inriktningsprogramvara)
| Originalförfattare | Robert C. Edgar |
|---|---|
| Utvecklare | köra5 |
| Initial release | 2004 |
| Stabil frisättning | 3.8.31 / 18 augusti 2016
|
| Förvar |
|
| Operativ system | Linux , macOS , Windows |
| Plattform | IA-32 , x86-64 |
| Tillgänglig i | engelsk |
| Typ | Multipelsekvensinriktning |
| Licens | Allmängods |
| Hemsida |
MUltiple Sequence Comparison by Log-Expectation ( MUSCLE ) är datorprogram för multipelsekvensinriktning av protein- och nukleotidsekvenser . Den är licensierad som allmän egendom . Metoden publicerades av Robert C. Edgar i två artiklar 2004. Den första artikeln, publicerad i Nucleic Acids Research , introducerade algoritmen för sekvensanpassning. Den andra uppsatsen, publicerad i BMC Bioinformatics , presenterade mer tekniska detaljer.
Algoritm
MUSKEL-algoritmen fortsätter i tre steg: utkastet progressiv , förbättrad progressiv och förfining .
Steg 1: Utkast till progressiv
I detta första steg producerar algoritmen en multipel justering, som betonar hastighet framför noggrannhet. Detta steg börjar med att beräkna k-mer- avståndet för varje par av ingångssekvenser för att skapa en avståndsmatris . UPGMA kluster avståndsmatrisen för att producera ett binärt träd . Från detta träd konstrueras en progressiv inriktning, som börjar med skapandet av profiler för varje blad av trädet. För varje nod i trädet konstrueras en parvis justering av de två underordnade profilerna, vilket skapar en ny profil som ska tilldelas den noden. Detta fortsätter tills det finns en multipelsekvensinriktning av alla inmatningssekvenser vid roten av trädet.
Steg 2: Förbättrad progressiv
Detta steg fokuserar på att erhålla ett mer optimalt träd genom att beräkna Kimura-avståndet för varje par av ingångssekvenser med användning av multipelsekvensinriktningen som erhölls i steg ett, och skapar en andra avståndsmatris. UPGMA grupperar denna avståndsmatris för att erhålla ett andra binärt träd. En progressiv anpassning utförs för att erhålla en multipelsekvensinriktning som i steg 1, men den optimeras genom att endast beräkna anpassningar i underträd vars förgreningsordningar har ändrats från det första binära trädet, vilket resulterar i en mer exakt anpassning.
Steg 3: Förfining
I detta sista skede väljs en kant från det andra trädet, med kanter som besöks i minskande avstånd från roten. Den valda kanten raderas, vilket delar upp trädet i två underträd. Profilen för multipelinriktningen beräknas sedan för varje underträd. En ny multipelsekvensinriktning produceras genom att omrikta underträdsprofilerna. Om SP-poängen förbättras behålls den nya justeringen, annars kasseras den. Processen att ta bort en kant och justera upprepas tills konvergens, eller tills en användardefinierad gräns nås.
Komplexitet och jämförelse
O( N 2 + NL + L 2 stegen av algoritmen är tidskomplexiteten . O( N 2L + NL 2 ) , rymdkomplexiteten är ) Förfiningssteget lägger till tidskomplexiteten ytterligare en term , O ( N3L ) . MUSCLE används ofta som en ersättning för Clustal , eftersom det vanligtvis (men inte alltid) ger bättre sekvensanpassningar, beroende på de valda alternativen. är betydligt snabbare än Clustal, mer så för större justeringar.
Algoritm Flödesschema
Integration
MUSCLE är integrerad i DNASTARs Lasergene-mjukvara, Geneious och MacVector och är tillgänglig i Sequencher , MEGA och UGENE som en plug-in . MUSCLE finns även tillgänglig som webbtjänst via European Molecular Biology Laboratory (EMBL) - European Bioinformatics Institute (EBI). I september 2016 har de två artiklarna som beskriver MUSCLE citerats mer än 19 000 gånger totalt.
