Detta dokument presenterar en metod för att klassificera en stor och blandad uppsättning okaraktäriserade sekvenser som tillhandahålls av genomprojekt. Som mått på sekvenslikviditet använder vi likhetspoäng som beräknas med en metod baserad på den dynamiska programmeringen (DP), såsom Smith-Waterman lokala anpassningsalgoritm. Även om jämförelse med DP-baserad metod är mycket känslig, när givna sekvenser inkluderar en familj av sekvenser som är mycket olika i evolutionsprocessen, likhet bland några av dem kan döljas bakom falska likheter av vissa orelaterade sekvenser. Även avståndet som härleds från likheten poäng får inte vara metrisk (dvs, triangeln ojämlikhet får inte hålla) när vissa sekvenser har multi-domain struktur. För att klara av dessa problem introducerar vi en ny grafstruktur som kallas p-quasi komplett graf för att beskriva en familj av sekvenser med en sammanfallsmått. Vi bevisar att en begränsad version av pquasi komplett graf problem (med tanke på ett positivt heltal k, om en graf innehåller en 0,5-quasi fullständig subgraph av vilken storlek ¿k eller inte) är NP-komplett. Således presenterar vi en approximation algoritm för att klassificera en uppsättning sekvenser med hjälp av p-quasi kompletta subgrafer. Hur effektiv vår metod är visas av resultatet av att klassificera över 4000 proteinsekvenser på Escherichia coli-genomet som helt bestämdes nyligen. c 1999 -Elsevier Science B.V. Alla rättigheter förbehållna
Matsuda m.fl. REF införde en grafstruktur kallad p-quasi komplett graf, som är densamma som de γ-quasi-kluster som definieras i detta papper, och de föreslog en approximationsalgoritm för att täcka alla hörn i en graf med ett minsta antal p-quasi kompletta subgrafer.
Classifying Molecular Sequences Using a Linkage Graph With Their Pairwise Similarities
{'venue': 'Theoretical Computer Science', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}