annotate TEisotools-1.0/commons/core/coord/SetUtils.py @ 6:20ec0d14798e draft

Uploaded

1 # Copyright INRA (Institut National de la Recherche Agronomique)
2 # http://www.inra.fr
3 # http://urgi.versailles.inra.fr
4 #
5 # This software is governed by the CeCILL license under French law and
6 # abiding by the rules of distribution of free software.  You can  use, 
7 # modify and/ or redistribute the software under the terms of the CeCILL
8 # license as circulated by CEA, CNRS and INRIA at the following URL
9 # "http://www.cecill.info". 
10 #
11 # As a counterpart to the access to the source code and  rights to copy,
12 # modify and redistribute granted by the license, users are provided only
13 # with a limited warranty  and the software's author,  the holder of the
14 # economic rights,  and the successive licensors  have only  limited
15 # liability. 
16 #
17 # In this respect, the user's attention is drawn to the risks associated
18 # with loading,  using,  modifying and/or developing or reproducing the
19 # software by the user in light of its specific status of free software,
20 # that may mean  that it is complicated to manipulate,  and  that  also
21 # therefore means  that it is reserved for developers  and  experienced
22 # professionals having in-depth computer knowledge. Users are therefore
23 # encouraged to load and test the software's suitability as regards their
24 # requirements in conditions enabling the security of their systems and/or 
25 # data to be ensured and,  more generally, to use and operate it in the 
26 # same conditions as regards security. 
27 #
28 # The fact that you are presently reading this means that you have had
29 # knowledge of the CeCILL license and that you accept its terms.
30 
31 
32 from commons.core.coord.Set import Set
33 
34 ## Static methods for the manipulation of Set instances
35 #
36 class SetUtils( object ):
37     
38     ## Change the identifier of each Set instance in the given list
39     #
40     # @param lSets list of Set instances
41     # @param newId new identifier
42     #
43     def changeIdInList(lSets, newId):
44         for iSet in lSets:
45             iSet.id = newId
46             
47     changeIdInList = staticmethod( changeIdInList )
48     
49     ## Return the length of the overlap between two lists of Set instances
50     #
51     # @param lSets1 list of Set instances
52     # @param lSets2 list of Set instances
53     # @return length of overlap
54     # @warning sequence names are supposed to be identical
55     #
56     def getOverlapLengthBetweenLists(lSets1, lSets2):
57         lSet1Sorted = SetUtils.getSetListSortedByIncreasingMinThenMax(lSets1)
58         lSet2Sorted = SetUtils.getSetListSortedByIncreasingMinThenMax(lSets2)
59         osize = 0
60         i = 0
61         j = 0
62         while i!= len(lSet1Sorted):
63             while j!= len(lSet2Sorted) and lSet1Sorted[i].getMin()>lSet2Sorted[j].getMax()\
64                 and not(lSet1Sorted[i].isOverlapping(lSet2Sorted[j])):
65                 j+=1
66             jj=j
67             while jj!= len(lSet2Sorted) and lSet1Sorted[i].isOverlapping(lSet2Sorted[jj]):
68                 osize+=lSet1Sorted[i].getOverlapLength(lSet2Sorted[jj])
69                 jj+=1
70             i+=1
71         return osize
72     
73     getOverlapLengthBetweenLists = staticmethod( getOverlapLengthBetweenLists )
74     
75     ## Return True if the two lists of Set instances overlap, False otherwise    
76     #
77     # @param lSets1 list of Set instances
78     # @param lSets2 list of Set instances
79     #    
80     def areSetsOverlappingBetweenLists( lSets1, lSets2 ):
81         lSet1Sorted = SetUtils.getSetListSortedByIncreasingMinThenMax(lSets1)
82         lSet2Sorted = SetUtils.getSetListSortedByIncreasingMinThenMax(lSets2)
83         i=0
84         j=0
85         while i!= len(lSet1Sorted):
86             while j!= len(lSet2Sorted) and lSet1Sorted[i].getMin()>lSet2Sorted[j].getMax()\
87                 and not(lSet1Sorted[i].isOverlapping(lSet2Sorted[j])):
88                 j+=1
89             if j!= len(lSet2Sorted) and lSet1Sorted[i].isOverlapping(lSet2Sorted[j]):
90                 return True
91             i+=1
92         return False
93     
94     areSetsOverlappingBetweenLists = staticmethod( areSetsOverlappingBetweenLists )
95     
96     ## Merge all overlapping Set instances between two lists of Set and give the next identifier 
97     #
98     # @param lSets1 list of Set instances
99     # @param lSets2 list of Set instances
00     # @param max_id start id value for inserting new Set
01     # @return a new list of the merged Set instances and the next identifier
02     # 
03     def getListOfMergedSetsAndNextId(lSets1, lSets2, max_id=0):
04         lSets_merged = []
05         list2merge = SetUtils.getListOfIdListOfOverlappingSets ( lSets1,lSets2 )
06         idlist1 = SetUtils.getDictOfListsWithIdAsKey(lSets1)
07         idlist2 = SetUtils.getDictOfListsWithIdAsKey(lSets2)
08         if max_id == 0:
09             max_id = max(idlist1.keys()) + 1
10         for i in list2merge:
11             if i == []:
12                 continue
13             l = []
14             min_id = max(i)
15             for j in i:
16                 if j>0:
17                     if min_id>j:
18                         min_id=j
19                     l.extend(idlist1[j])
20                     del idlist1[j]
21                 else:
22                     l.extend(idlist2[j*-1])
23                     del idlist2[j*-1]
24             l = SetUtils.mergeSetsInList(l)
25             SetUtils.changeIdInList(l, min_id)
26             lSets_merged.extend(l)
27         for id, alist in idlist1.items():
28             lSets_merged.extend(alist)
29         for id,alist in idlist2.items():
30             SetUtils.changeIdInList(alist,max_id)
31             lSets_merged.extend(alist)
32             max_id+=1
33         return lSets_merged, max_id
34     
35     getListOfMergedSetsAndNextId = staticmethod ( getListOfMergedSetsAndNextId )
36     
37 #    ## Concatenate two Set instance lists and give the next identifier 
38 #    #
39 #    # @param lSets1 list of Set instances
40 #    # @param lSets2 list of Set instances
41 #    # @param maxId start id value for inserting new Set
42 #    # @return a new list of Set instances and the next identifier
43 #    # 
44 #    @staticmethod
45 #    def getSetsListOfTwoConcatenatedSetsListAndNextId(lSets1, lSets2, maxId = 0):
46 #        lOutSets = lSets1
47 #        dId2SetsList2 = SetUtils.getDictOfListsWithIdAsKey(lSets2)
48 #        if maxId == 0:
49 #            dId2SetsList1 = SetUtils.getDictOfListsWithIdAsKey(lSets1)
50 #            maxId = max(dId2SetsList1.keys())
51 #        for lSets in dId2SetsList2.values():
52 #            SetUtils.changeIdInList(lSets, maxId)
53 #            lOutSets.extend(lSets)
54 #            maxId += 1
55 #        return lOutSets, maxId
56     
57     ## Return the sum of the length of each Set instance in the given list
58     #
59     # @param lSets: list of Set instances
60     #
61     def getCumulLength(lSets):
62         length = 0
63         for i in lSets:
64             length += i.getLength()
65         return length
66     
67     getCumulLength = staticmethod( getCumulLength )
68     
69     ## Return a tuple with min and max coordinates of Set instances in the given list
70     #
71     # @param lSets list of Set instances
72     # 
73     def getListBoundaries(lSets):
74         qmin = -1
75         qmax = -1
76         for iSet in lSets:
77             if qmin == -1:
78                 qmin = iSet.start
79             qmin = min(qmin, iSet.getMin())
80             qmax = max(qmax, iSet.getMax())
81         return (qmin, qmax)
82     
83     getListBoundaries = staticmethod( getListBoundaries )
84     
85     ## Show Set instances contained in the given list
86     #
87     # @param lSets list of Set instances
88     # 
89     def showList(lSets):
90         for iSet in lSets:
91             iSet.show()
92             
93     showList = staticmethod( showList )
94     
95     ## Write Set instances contained in the given list
96     #
97     # @param lSets list of Set instances
98     # @param fileName a file name
99     # @param mode the open mode of the file '"w"' or '"a"' 
00     #
01     def writeListInFile(lSets, fileName, mode="w"):
02         fileHandler = open(fileName, mode)
03         for iSet in lSets:
04             iSet.write(fileHandler)
05         fileHandler.close()
06         
07     writeListInFile = staticmethod( writeListInFile )
08     
09     ## Split a Set list in several Set lists according to the identifier
10     #
11     # @param lSets list of Set instances
12     # @return a dictionary which keys are identifiers and values Set lists
13     #
14     def getDictOfListsWithIdAsKey(lSets):
15         dId2SetList = {}
16         for iSet in lSets:
17             if dId2SetList.has_key(iSet.id):
18                 dId2SetList[iSet.id].append(iSet)
19             else:
20                 dId2SetList[iSet.id] = [iSet]
21         return dId2SetList
22     
23     getDictOfListsWithIdAsKey = staticmethod( getDictOfListsWithIdAsKey )
24     
25     
26     ## Split a Set list in several Set lists according to the identifier
27     #
28     # @param lSets list of Set instances
29     # @return a dictionary which keys are identifiers and values Set lists
30     #
31     def getDictOfListsWithIdAsKeyFromFile( setFile ):
32         dId2SetList = {}
33         setFileHandler = open( setFile, "r" )
34         while True:
35             line = setFileHandler.readline()
36             if line == "":
37                 break
38             iSet = Set()
39             iSet.setFromTuple( line[:-1].split("\t") )
40             if not dId2SetList.has_key( iSet.id ):
41                 dId2SetList[ iSet.id ] = []
42             dId2SetList[ iSet.id ].append( iSet )
43         setFileHandler.close()
44         return dId2SetList
45     
46     getDictOfListsWithIdAsKeyFromFile = staticmethod( getDictOfListsWithIdAsKeyFromFile )
47     
48     
49     ## Return a Map list from the given Set List
50     #
51     # @param lSets list of Set instances
52     # 
53     def getMapListFromSetList(lSets):
54         lMaps = []
55         for iSet in lSets:
56             lMaps.append(iSet.set2map())
57         return lMaps
58     
59     getMapListFromSetList = staticmethod( getMapListFromSetList )
60     
61     ## Construct a Set list from a Map list
62     #
63     # @param lMaps list of Map instances
64     # 
65     def getSetListFromMapList(lMaps):
66         lSets = []
67         c = 0
68         for iMap in lMaps:
69             c += 1
70             lSets.append( Set(c, iMap.name, iMap.seqname, iMap.start, iMap.end) )
71         return lSets
72     
73     getSetListFromMapList = staticmethod( getSetListFromMapList )
74     
75     ## Merge all overlapping Set instances in a list without considering the identifiers.
76     #  Start by sorting Set instances by their increasing Min coordinate.
77     #
78     # @return: a new list of the merged Set instances
79     #
80     def mergeSetsInList(lSets):
81         l=[]
82         if len(lSets)==0:
83             return l
84         
85         lSortedSets = SetUtils.getSetListSortedByIncreasingMinThenInvLength( lSets )
86         
87         prev_count = 0
88         for iSet in lSortedSets[0:]:
89             if prev_count != len(lSortedSets):
90                 for i in lSortedSets[ prev_count + 1: ]:
91                     if iSet.isOverlapping( i ):
92                         iSet.merge( i )
93                 IsAlreadyInList = False
94                 for newSet in l:
95                     if newSet.isOverlapping( iSet ):
96                         IsAlreadyInList = True
97                         newSet.merge( iSet )
98                         l [ l.index( newSet ) ] = newSet
99                 if not IsAlreadyInList:
00                     l.append( iSet )
01                 prev_count += 1
02         return l
03     
04     mergeSetsInList = staticmethod( mergeSetsInList )
05     
06     ## Unjoin a Set list according to another
07     #
08     # @param lToKeep: a list of Set instances to keep 
09     # @param lToUnjoin: a list of Set instances to unjoin
10     # @return: lToUnjoin split in several list
11     #    
12     def getSetListUnjoined(lToKeep, lToUnjoin):
13         lSortedToKeep = SetUtils.getSetListSortedByIncreasingMinThenMax( lToKeep )
14         lSortedToUnjoin = SetUtils.getSetListSortedByIncreasingMinThenMax( lToUnjoin )
15         if lSortedToUnjoin == []:
16             return []
17         if lSortedToKeep == []:
18             return [ lSortedToUnjoin ]
19         
20         i=0
21         resultListSet=[]
22         while i<len(lSortedToKeep):
23             j1=0
24             while j1<len(lSortedToUnjoin) and lSortedToKeep[i].getMin() > lSortedToUnjoin[j1].getMax():
25                 j1+=1
26             if j1==len(lSortedToUnjoin):
27                 break
28             if j1!=0:
29                 resultListSet.append(lSortedToUnjoin[:j1])
30                 del lSortedToUnjoin[:j1]
31                 j1=0
32             if i+1==len(lSortedToKeep):
33                 break
34             j2=j1
35             if j2<len(lSortedToUnjoin) and lSortedToKeep[i+1].getMin() > lSortedToUnjoin[j2].getMax():
36                 while j2<len(lSortedToUnjoin) and lSortedToKeep[i+1].getMin() > lSortedToUnjoin[j2].getMax():
37                     j2+=1
38                 resultListSet.append(lSortedToUnjoin[j1:j2])
39                 del lSortedToUnjoin[j1:j2]
40             i+=1
41     
42         if resultListSet!=[] or i == 0:
43             resultListSet.append(lSortedToUnjoin)
44         return resultListSet
45     
46     getSetListUnjoined = staticmethod(getSetListUnjoined)
47       
48     ## Return new list of Set instances with no duplicate
49     #
50     # @param lSets list of Set instances
51     #
52     def getSetListWithoutDuplicates( lSets ):
53         if len(lSets) < 2:
54             return lSets
55         lSortedSet = SetUtils.getSetListSortedByIncreasingMinThenMax( lSets )
56         lUniqSet = [ lSortedSet[0] ]
57         for iSet in lSortedSet[1:]:
58             if iSet != lUniqSet[-1]:
59                 lUniqSet.append( iSet )
60         return lUniqSet
61     
62     getSetListWithoutDuplicates = staticmethod( getSetListWithoutDuplicates )
63     
64     ## Return a list of Set instances sorted in increasing order according to the Min, then the Max, and finally their initial order
65     #
66     # @param lSets: list of Set instances
67     #
68     def getSetListSortedByIncreasingMinThenMax( lSets ):
69         return sorted( lSets, key=lambda iSet: ( iSet.getMin(), iSet.getMax() ) )
70     
71     getSetListSortedByIncreasingMinThenMax = staticmethod( getSetListSortedByIncreasingMinThenMax )
72     
73     ## Return a list of Set instances sorted in increasing order according to the min, then the inverse of the length, and finally their initial order
74     #
75     # @param lSets: list of Set instances
76     #
77     def getSetListSortedByIncreasingMinThenInvLength( lSets ):
78         return sorted( lSets, key=lambda iSet: ( iSet.getMin(), 1 / float(iSet.getLength()) ) )
79     
80     getSetListSortedByIncreasingMinThenInvLength = staticmethod( getSetListSortedByIncreasingMinThenInvLength )
81  
82     ## Return a list of Set instances sorted in increasing order according to the SeqName, then the Name, then the Min, then the Max and finally their initial order
83     #
84     # @param lSets: list of Set instances
85     #   
86     def getSetListSortedBySeqThenRegionThenMinThenMax(lSets):
87         return sorted(lSets, key=lambda iSet: (iSet.getSeqname(), iSet.getName(), iSet.getMin(), iSet.getMax()))
88     
89     getSetListSortedBySeqThenRegionThenMinThenMax = staticmethod(getSetListSortedBySeqThenRegionThenMinThenMax)
90     
91     ## Return a list of identifier lists of overlapping Sets from the subject list, according to the reference list
92     #
93     # @param lRef list of Set instances
94     # @param lSubject list of Set instances
95     #
96     def getListOfIdListOfOverlappingSets(lRef,lSubject):
97         lSortedRef = SetUtils.getSetListSortedByIncreasingMinThenMax( lRef )
98         lSortedSubject = SetUtils.getSetListSortedByIncreasingMinThenMax( lSubject )
99 
00         lOverlappingSet = []
01         lOverlappingSetCounter = 0
02 
03         id2LOverlappingSet_pos = {}
04     
05         i = 0
06         j = 0
07         while i!= len(lSortedRef):
08             while j!= len(lSortedSubject) and lSortedRef[i].getMin()>lSortedSubject[j].getMax()\
09                 and not(lSortedRef[i].isOverlapping(lSortedSubject[j])\
10                       and lSortedRef[i].isOnDirectStrand()==lSortedSubject[j].isOnDirectStrand()):
11                 j+=1
12             jj=j
13             while jj!= len(lSortedSubject) and lSortedRef[i].isOverlapping(lSortedSubject[jj])\
14                   and lSortedRef[i].isOnDirectStrand()==lSortedSubject[jj].isOnDirectStrand():
15                 id1=lSortedRef[i].id
16                 id2=lSortedSubject[jj].id*-1
17                 if id2LOverlappingSet_pos.has_key(id1) \
18                    and not id2LOverlappingSet_pos.has_key(id2):
19                     lOverlappingSet[id2LOverlappingSet_pos[id1]].append(id2)
20                     id2LOverlappingSet_pos[id2]=id2LOverlappingSet_pos[id1]
21                 if id2LOverlappingSet_pos.has_key(id2) \
22                    and not id2LOverlappingSet_pos.has_key(id1):
23                     lOverlappingSet[id2LOverlappingSet_pos[id2]].append(id1)
24                     id2LOverlappingSet_pos[id1]=id2LOverlappingSet_pos[id2]
25                 if not id2LOverlappingSet_pos.has_key(id2) \
26                    and not id2LOverlappingSet_pos.has_key(id1):
27                     lOverlappingSet.append([id1,id2])
28                     id2LOverlappingSet_pos[id1]=lOverlappingSetCounter
29                     id2LOverlappingSet_pos[id2]=lOverlappingSetCounter
30                     lOverlappingSetCounter+=1
31                 jj+=1
32             i+=1
33     
34         return lOverlappingSet
35     
36     getListOfIdListOfOverlappingSets = staticmethod (getListOfIdListOfOverlappingSets)
37     
38     ## Return a list of sets without overlapping between two lists of sets
39     #
40     # @param lSet1 and lSet2 
41     #
42     def getListOfSetWithoutOverlappingBetweenTwoListOfSet(lSet1, lSet2):
43         for i in lSet1:
44             for idx,j in enumerate(lSet2):
45                 n=j.diff(i)
46                 if not n.isEmpty() and n.getLength()>=20:
47                     lSet2.append(n)
48         lSet2WithoutOverlaps=[]
49         for i in lSet2:
50             if not i.isEmpty() and i.getLength()>=20:
51                 lSet2WithoutOverlaps.append(i)
52         return lSet2WithoutOverlaps
53         
54     getListOfSetWithoutOverlappingBetweenTwoListOfSet = staticmethod (getListOfSetWithoutOverlappingBetweenTwoListOfSet)
55 
56     ## Return a Set list from a Set file
57     #
58     # @param setFile string name of a Set file
59     # @return a list of Set instances
60     #
61     def getSetListFromFile( setFile ):
62         lSets = []
63         setFileHandler = open( setFile, "r" )
64         while True:
65             line = setFileHandler.readline()
66             if line == "":
67                 break
68             iSet = Set()
69             iSet.setFromString( line )
70             lSets.append( iSet )
71         setFileHandler.close()
72         return lSets
73     
74     getSetListFromFile = staticmethod( getSetListFromFile )
75     
76     
77     def convertSetFileIntoMapFile( setFile, mapFile ):
78         setFileHandler = open( setFile, "r" )
79         mapFileHandler = open( mapFile, "w" )
80         iSet = Set()
81         while True:
82             line = setFileHandler.readline()
83             if line == "":
84                 break
85             iSet.setFromString( line )
86             iMap = iSet.getMapInstance()
87             iMap.write( mapFileHandler )
88         setFileHandler.close()
89         mapFileHandler.close()
90         
91     convertSetFileIntoMapFile = staticmethod( convertSetFileIntoMapFile )
92 
93 
94     def getDictOfListsWithSeqnameAsKey( lSets ):
95         dSeqnamesToSetList = {}
96         for iSet in lSets:
97             if not dSeqnamesToSetList.has_key( iSet.seqname ):
98                 dSeqnamesToSetList[ iSet.seqname ] = []
99             dSeqnamesToSetList[ iSet.seqname ].append( iSet )
00         return dSeqnamesToSetList
01     
02     getDictOfListsWithSeqnameAsKey = staticmethod( getDictOfListsWithSeqnameAsKey )
03     
04     
05     def filterOnLength( lSets, minLength=0, maxLength=10000000000 ):
06         if minLength == 0 and maxLength == 0:
07             return lSets
08         lFiltered = []
09         for iSet in lSets:
10             if minLength <= iSet.getLength() <= maxLength:
11                 lFiltered.append( iSet )
12         return lFiltered
13     
14     filterOnLength = staticmethod( filterOnLength )
15     
16     
17     def getListOfNames( setFile ):
18         lNames = []
19         setFileHandler = open( setFile, "r" )
20         iSet = Set()
21         while True:
22             line = setFileHandler.readline()
23             if line == "":
24                 break
25             iSet.setFromTuple( line[:-1].split("\t") )
26             if iSet.name not in lNames:
27                 lNames.append( iSet.name )
28         setFileHandler.close()
29         return lNames
30     
31     getListOfNames = staticmethod( getListOfNames )
32 
33 
34     def getDictOfDictsWithNamesThenIdAsKeyFromFile( setFile ):
35         dNames2DictsId = {}
36         setFileHandler = open( setFile, "r" )
37         while True:
38             line = setFileHandler.readline()
39             if line == "":
40                 break
41             iSet = Set()
42             iSet.setFromTuple( line[:-1].split("\t") )
43             if not dNames2DictsId.has_key( iSet.name ):
44                 dNames2DictsId[ iSet.name ] = { iSet.id: [ iSet ] }
45             else:
46                 if not dNames2DictsId[ iSet.name ].has_key( iSet.id ):
47                     dNames2DictsId[ iSet.name ][ iSet.id ] = [ iSet ]
48                 else:
49                     dNames2DictsId[ iSet.name ][ iSet.id ].append( iSet )
50         setFileHandler.close()
51         return dNames2DictsId
52     
53     getDictOfDictsWithNamesThenIdAsKeyFromFile = staticmethod( getDictOfDictsWithNamesThenIdAsKeyFromFile )