Maximal unique match
મેક્સિમલ યુનિક મેચ અથવા એમયુએમ, ટૂંકમાં, કોમ્પ્યુટેશનલ બાયોલોજીમાં જીનોમના બહુવિધ અનુક્રમ સંરેખણમાં ચાવીરૂપ પગલાનો એક ભાગ છે. એમયુએમ અને અન્ય સંભવિત એન્કરની ઓળખ એ એમયુએમઆર જેવી મોટી સંરેખણ પ્રણાલીઓનું પ્રથમ પગલું છે. એન્કર એ બે જીનોમ વચ્ચેના વિસ્તારો છે જ્યાં તેઓ ખૂબ સમાન હોય છે. એમયુએમ શું છે તે સમજવા માટે આપણે ટૂંકાક્ષરમાં દરેક શબ્દને વ્યક્તિગત રીતે તોડી શકીએ છીએ. મેળ સૂચવે છે કે સબસ્ટ્રિંગ સંરેખિત થવા માટે બંને ક્રમમાં થાય છે. અનન્યનો અર્થ એ છે કે સબસ્ટ્રિંગ દરેક ક્રમમાં માત્ર એક જ વાર આવે છે. છેવટે, મહત્તમ જણાવે છે કે સબસ્ટ્રિંગ અન્ય મોટી સ્ટ્રિંગનો ભાગ નથી જે અગાઉની બંને જરૂરિયાતોને પૂર્ણ કરે છે. આની પાછળનો વિચાર એ છે કે લાંબા ક્રમ જે બરાબર મેળ ખાય છે અને દરેક જિનોમમાં માત્ર એક જ વાર થાય છે તે લગભગ ચોક્કસપણે વૈશ્વિક સંરેખણનો ભાગ છે. ઔપચારિક વ્યાખ્યા "બે જીનોમ એ અને બીને જોતાં, મેક્સિમલ યુનિક મેચ (એમયુએમ) સબસ્ટ્રિંગ એ ચોક્કસ લઘુત્તમ લંબાઈ ડી (મૂળભૂત રીતે ડી = 20) કરતા લાંબી લંબાઈની એ અને બીની સામાન્ય સબસ્ટ્રિંગ છે, જેમ કે તે મહત્તમ છે, એટલે કે, તેને બે છેડા પર વિસંગતતા કર્યા વિના વિસ્તૃત કરી શકાતી નથી; અને તે બંને સિક્વન્સમાં અનન્ય છે" એલ્ગોરિધમ બે ખૂબ લાંબા જીનોમ સિક્વન્સમાં એમયુએમના સમૂહને ઓળખવું એ ગણતરીત્મક રીતે તુચ્છ નથી. બહુવિધ અનુક્રમ સંરેખણમાં એમયુએમને ઓળખવા માટે ઘણી અલ્ગોરિધમિક રીતો છે. સૌથી સરળ અને સૌથી ધીમી પદ્ધતિ બ્રુટ ફોર્સનો ઉપયોગ કરવાની છે જ્યાં જીનોમમાં દરેક અનુક્રમણિકા અને જીનોમમાં દરેક અનુક્રમણિકા માટે, તમે અને ના સૌથી લાંબા સામાન્ય ઉપસર્ગની ગણતરી કરો છો. આગળ તમારે ખાતરી કરવી જ જોઇએ કે ઓછામાં ઓછી લંબાઈ ઓછામાં ઓછી એમયુએમ કદ ક્યાં નિર્દિષ્ટ છે. છેવટે તમારે ખાતરી કરવી પડશે કે તે બંને જીનોમમાં અનન્ય છે. બ્રુટ ફોર્સ પદ્ધતિની જટિલતા આમ છે. વાસ્તવિકતામાં એમયુએમને અને માટે સામાન્યીકૃત પ્રત્યય વૃક્ષ બનાવીને ઓળખવામાં આવે છે. ત્યારબાદ દરેક જીનોમ ક્રમમાંથી બરાબર એક બાળક સાથે તમામ આંતરિક ગાંઠો માટે એક યાદી બનાવવામાં આવે છે. આ દરેક ગાંઠો માટે (આપણે જિનોમમાંથી બાળકોને અને જિનોમમાંથી બાળકોને ઓળખીશું) તે તપાસો અને જ્યાં આ શરતો હોય છે, ત્યાં આપણે જાણી શકીએ છીએ કે આ એક એમયુએમ છે. આ કિસ્સામાં જટિલતા ઘટાડવામાં આવે છે. નીચે આપેલા ચિત્રમાં પ્રારંભિક શબ્દમાળાઓ અને 1 ના એ, એમયુએમ જી અને ટીએ હોવા જોઈએ. લાલ પાંદડું સૂચવે છે કે પાંદડું સ્ટ્રિંગ S માંથી આવ્યું છે અને વાદળી પાંદડું સ્ટ્રિંગ સૂચવે છે. A પર આંતરિક નોડને કાઢી નાખવામાં આવ્યો હતો કારણ કે જેનો અર્થ થાય છે કે બંને A ની પહેલાં જે અક્ષર આવે છે તે સમાન (T) છે, આ એવી સ્થિતિ છે જ્યાં સિક્વન્સ મોટા અનન્ય ક્રમ સાથે સંબંધિત છે. સી ખાતેના આંતરિક નોડને કાઢી નાખવામાં આવે છે કારણ કે તેમાં એસના બે બાળકો છે. આ આપણને જી અને ટીએના એમયુએમ સાથે છોડી દે છે. ઉદાહરણ એમયુએમને વધુ સમજાવવા માટે, આપણે નીચેનું ઉદાહરણ લઈએ છીએ. ચાલો આપણે કહીએ કે d = 3 અને આપણા બે જીનોમ નીચે મુજબ છેઃ S = CTACTCTCATCTCTCAGTCATCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCAGTCT $TGT લંબાઈમાં ઓછામાં ઓછું d છે, બંને ક્રમમાં માત્ર એક જ વાર થાય છે, અને ડાબી બાજુના અક્ષરો અને એક ઉદાહરણને સમજાવવા માટે કે જ્યાં અમારું એમયુએમ મોટા ક્રમનો ભાગ નથી અને અનન્ય છે તેની ખાતરી કરવા માટે વિસ્તરણની જરૂર છે, નીચેની બાબતો લોઃ S = CTACCCTCTAAGTCATCGCGCTGGCTTT #T = CTGGCTAAGTCTCGTCTGGCTT $એ. ટી. જી. ને એમયુએમ તરીકે પરીક્ષણ કરવાના કિસ્સામાં બે સમસ્યાઓ છે કારણ કે એટીજી અનન્ય નથી અને તે અહીં દર્શાવ્યા મુજબ મોટા અનુગામીનો પણ ભાગ છેઃ S = CTACCCTCTAAGTCAGGCTGCTGTCTTT #T = CTGGCTAAGTCTGCGGTTT $તેથી આ ક્રમનું વિસ્તરણ આ પદ્ધતિનો ઉપયોગ કરીને પુનરાવર્તિત રીતે એક અંતિમ ઉત્પાદન ઉત્પન્ન થાય છે જ્યાં દરેક એમયુએમને સ્પષ્ટતા માટે ઓળખવામાં આવે છે અને દરેક એમયુએમ રંગીન-કોડેડ હોય છેઃ એસ = સીટીએસીસીજી #ટી = એસીટીટીજીટી $મેક્સિમલ એક્ઝેક્ટ મેચ (એમઇએમ) એમયુએમ એ મેક્સિમલ એક્ઝેક્ટ મેચો અથવા એમઇએમએસ તરીકે ઓળખાતા મોટા સમૂહનો સબસેટ છે. એમ. ઇ. એમ. માં એમ. યુ. એમ. ની વિશિષ્ટતાની સ્થિતિ હળવી હોય છે. એમઇએમ સ્થાનિક સંરેખણ જેવા છે પરંતુ આ કિસ્સામાં માત્ર એવા ક્રમને ઓળખે છે જ્યાં કોઈ અંતર નથી. એમયુએમર સિક્વન્સ સંરેખણ બહુવિધ સિક્વન્સ સંરેખણ સંદર્ભો સિક્વન્સ સંરેખણ અલ્ગોરિધમ્સ પણ જુઓ.