annotate Process/PipelineAlignment.py @ 2:46fb79167a61 tip

Main Code

'''
Created on 10/11/2014

@organization: Lancaster University & University of Leeds
@version: 1.0
Created on 11/12/2014

@author: Victor Padilla
@contact: [e-mail]

Functions related to the alignment
and voting process
'''
from Alignment import FastAlignmentArrays
from SymbolConversion import SymbolConversion
from Functions import FilesFunctions
import numpy as np
from Clustering import Clustering
import math
from Alignment import NWunsch


class PipelineAlignment:
    def alignGround(self,OMRs,part):
        '''
        Returns one part and the ground aligned. The first array value of OMRs 
        should be the ground and the second the omr to align
        '''
        sc=SymbolConversion()
        OMRs_symbols=[]
        omr_symbolsAlign=[]
        for omr in OMRs:
            omr_symbols=sc.filterOMR(omr,part)[1]
            OMRs_symbols.append(omr_symbols)
            omr_symbolsAlign.append([])
        
        faa=FastAlignmentArrays()
        out=faa.needleman_wunsch(OMRs_symbols[0], OMRs_symbols[1])[0]

             
        return out
    
    def getDistances(self,OMRs_symbols):
        '''
        Returns the distance matrix from several omr
        in symbols, using the first symbol only
        [u'N:E-4_0.25', 0.25, '', 2.75, 3.0, None] y
        [u'N:E-4_0.25', 0.33, '', 2.50, 2.75, None]
        
        are equals
        
        Returns a triangular matrix
        [[ 0.          0.17647058  0.19141912]
         [ 0.          0.          0.17647058]
         [ 0.          0.          0.        ]]
        
        Uses the algorithm implemented in C for increasing the speed 
        Alignment/C_Libraries/NWunsch
        '''
        ls=len(OMRs_symbols)
        dimension= (ls,ls)
        distances=np.zeros(dimension)   
        for i in range(len(OMRs_symbols)):  
            for j in range(i+1,len(OMRs_symbols)):
                print i,j
                align1=[]
                align2=[]
                for s in OMRs_symbols[i]:
                    align1.append(s[0])
                for s in OMRs_symbols[j]:
                    align2.append(s[0])
                #Algorithm implemented in C
                if len(align1)==0 or len(align2)==0:
                    score=0
                else:
                    print"-------------------------"  
                    
                    score=NWunsch.NWunsch_getSimilarity(align1,align2)
                    print"-------------------------"  
                if math.isnan(score):
                    score=0
                distances[i][j]=1-score      
        return distances
    
    def getDistanceLength(self,OMRs_symbols):
        '''
        Similar to getDistance, but based on the length
        of the omrs. Testing purposes
        '''
        ls=len(OMRs_symbols)
        dimension= (ls,ls)
        distances=np.zeros(dimension)       
        for i in range(len(OMRs_symbols)):       
            for j in range(i+1,len(OMRs_symbols)):
                print i,j
                len_i=len(OMRs_symbols[i])
                len_j=len(OMRs_symbols[j])
                maxLen=len_j
                if len_i>=len_j:
                    maxLen=len_i
                
                score=(len_i-len_j)*1.0/maxLen
                if score<0:
                    score=score*-1
                distances[i][j]=score        
        return distances
    
    def __getMinimum(self,distance):
        '''
        Returns the minimum value and the x,y position
        in the distance matrix
        '''
        minim=1000
        iMin=0
        jMin=0
        for i in range(len(distance[0])):         
            for j in range(i+1,len(distance[0])):
                dist=distance[i][j]
                if isinstance(dist,list):
                    dist=dist[0]
                if dist<minim:
                    minim=dist
                    iMin=i
                    jMin=j
                    
        return minim,iMin,jMin
    
    
    def __recalculeDistances(self,distance,iMin,jMin):
        '''
        Removes the rows and the column in the distance matrix
        and calculates the new matrix 
        '''
        for i in range(len(distance[0])):         
            for j in range(i+1,len(distance[0])):       
                if j==iMin:
                    dist=distance[i][j]
                    dist2=distance[i][jMin]
                    distance[i][j]=(dist+dist2)/2
        distance=np.delete(distance, jMin, 0)
        distance=np.delete(distance, jMin, 1)     
        return distance
    
    
    def __getPairingReal(self,iMin,jMin,removedArray):
        '''
        Returns the real omr position in the original matrix 
        based on the actual position and the elements removed
        
        usage:
        self._getPairingReal(0,1,[1])
        returns
        0,2
        '''
        iMinReal=iMin
        jMinReal=jMin
        removedArray.sort()
        for removedItem in removedArray:
            if iMinReal>=removedItem:
                iMinReal+=1
            if jMinReal>=removedItem:
                jMinReal+=1
        return iMinReal,jMinReal
    
    def selectBetterOMRs(self,OMRs_symbols):
        '''
        Based on Philogenetic trees, this function
        takes the best omrs based on the distances between them
        '''
        distanceSimple=self.getDistances(OMRs_symbols)  
        clustering=Clustering()
        distances=clustering.getCompleteMatrix(distanceSimple)  
        species = []
        for i in range(len(OMRs_symbols)):
            species.append(i)
        clu = clustering.make_clusters(species)    
        tree = clustering.regroup(clu, distances)

        #at least 3 leafs in the tree
        maintree=tree
        for i in range(3,len(OMRs_symbols)):
            maintree=clustering.getBetterTree(tree,i)
            if len(clustering.getLeafs(maintree))>=3:
                break
           
            
        betterOmrIds= clustering.getLeafs(maintree) 
        
        #Graphic representation
        strTree=clustering.getStringTree(tree,tree.height,"")
        print strTree
        clustering.showTree(strTree)
        strMainTree=clustering.getStringTree(maintree,maintree.height,"")
        print strMainTree
        clustering.showTree(strMainTree)

        newOMRs=[]
        for i in betterOmrIds:
            newOMRs.append(OMRs_symbols[i])

        return newOMRs,betterOmrIds
    
#     def alignNJ(self,idPart,fsOMRs,partOMRs):
#         '''
#         Main function for aligning the different OMRs
#         
#         Returns:
#             omr_symbolsAligned. OMR array of symbols aligned (only the best)
#             betterOmrIds. Id array of better OMRs (for writing the log file)
#         
#         usage:
#             pa=PipelineAlignment()
#             omr_symbolsAligned,betterOmrIds=pa.alignNJ(idPart,fsOMRs,partOMRs)
#         '''
#         
# 
#         OMRs_symbols=[]
#         sc=SymbolConversion()
#         print "2---converting to symbols---"
#         for omr in OMRs:
#             if omr!=[]:
#                 omr_symbols=sc.filterOMR(omr,idPart)[1]
#                 OMRs_symbols.append(omr_symbols)
#             else:
#                 OMRs_symbols.append([])
#             
#         print "3---removing worst OMR---"  
# #         betterOmrIds=[]
#         OMRs_symbols,betterOmrIds=self.selectBetterOMRs(OMRs_symbols)
# 
#         print "4---calculating distances---"
#         distances=self.getDistances(OMRs_symbols)
#         
#         print "5---aligning symbols---"
#                
#         omr_symbolsAligned=self.setOMRSymbolsAligned(OMRs_symbols,distances)
#         
#         return omr_symbolsAligned,betterOmrIds
    
    def alignNJ_files(self,idPart,fsOMRs_files,partOMRs_files):
        '''
        Main function for aligning the different OMRs
        
        Returns:
            omr_symbolsAligned. OMR array of symbols aligned (only the best)
            betterOmrIds. Id array of better OMRs (for writing the log file)
        
        usage:
            pa=PipelineAlignment()
            omr_symbolsAligned,betterOmrIds=pa.alignNJ(idPart,fsOMRs,partOMRs)
        '''
        
               
        ff=FilesFunctions()
        OMRs_files=partOMRs_files+fsOMRs_files
        OMRs_symbols=[]
        sc=SymbolConversion()
        print "2---converting to symbols---"
        for omr_file in OMRs_files:
            omr=ff.getOMR(omr_file)
            if omr!=[]:
                omr_symbols=sc.filterOMR(omr,idPart)[1]
                OMRs_symbols.append(omr_symbols)
            else:
                OMRs_symbols.append([])
            
        print "3---removing worst OMR---"  
#         betterOmrIds=[]

        
        OMRs_symbols,betterOmrIds=self.selectBetterOMRs(OMRs_symbols)

        print "4---calculating distances---"
        distances=self.getDistances(OMRs_symbols)
        
        print "5---aligning symbols---"
               
        omr_symbolsAligned=self.setOMRSymbolsAligned(OMRs_symbols,distances)
        
        return omr_symbolsAligned,betterOmrIds
    def __setVoidArray(self,length):
        '''
        private function to create a void array
        '''
        arrayOut=[]
        for _ in range(length):
            arrayOut.append([])

        return arrayOut
            
    def setOMRSymbolsAligned(self,OMRs_symbols,distances):   
        '''
        returns the OMRs symbols aligned from OMR symbols and 
        the distances matrix
        ''' 
        pairings=[]
        pairingsReal=[]
        gapArray=[]
        removedArray=[]
        omr_symbolsAlign=self.__setVoidArray(len(OMRs_symbols))
        faa=FastAlignmentArrays()
        while len(distances[0])>1:
            minim,iMin,jMin=self.__getMinimum(distances)
            print distances,minim,iMin,jMin
            pairings.append([iMin,jMin])
            iMinReal,jMinReal=self.__getPairingReal(iMin,jMin,removedArray)
            
            pairingsReal.append([iMinReal,jMinReal])
            if len(omr_symbolsAlign[iMinReal])==0:
                omr_symbolsAlign[iMinReal]=OMRs_symbols[iMin]
            if len(omr_symbolsAlign[jMinReal])==0:
                omr_symbolsAlign[jMinReal]=OMRs_symbols[jMin]
                
            out=faa.needleman_wunsch(omr_symbolsAlign[iMinReal], omr_symbolsAlign[jMinReal])[0]
            omr_symbolsAlign[iMinReal]=out[0]
            omr_symbolsAlign[jMinReal]=out[1]
            gap1=out[2]
            gap2=out[3]
            gapArray.append([gap1,gap2])
            

            OMRs_symbols.pop(jMin)
            removedArray.append(jMinReal)
            
            distances=self.__recalculeDistances(distances,iMin,jMin)
            
                
        omr_symbolsAlign=self.__fillingGaps(omr_symbolsAlign,gapArray,pairingsReal)


        return omr_symbolsAlign
    
    def __fillingGaps(self,omr_symbolsAlign,gapArray,pairingsReal):
        '''
        private function to complete gaps based on the gap matrix 
        and the pairs stablished
        '''
        for p in range(len(pairingsReal)-1,0,-1):
            for i in range(2):
                for j in range(2):
                    for t in range(1,p+1):
                        if(pairingsReal[p][i]==pairingsReal[p-t][j]):
                            if j==0:
                                s=1
                            if j==1:
                                s=0
                            omrIndex=pairingsReal[p-t][s]
                            newGap=[]
                            for gap in gapArray[p][i]:
                                omr_symbolsAlign[omrIndex].insert(gap,"*")   
                                newGap.append(gap)
                            gapArray[p-t][s]=gapArray[p-t][s]+newGap
                                

        return omr_symbolsAlign